Panlab: Brewing IDEAS

uvic cs core courses

Section II
The following list of the nine computer science areas shows the learning outcomes for the corresponding
University of Victoria Department of Computer Science 300-level course that covers each area. This
information provides guidance on the skills and knowledge required to cover the corresponding areas. A
substantial (but not perfect) match is expected for courses in Table A.

1. Operating Systems
UVic corresponding course: CSC 360 Operating Systems
Students will be able to understand the data structures and algorithms for the main components in a modern
operating system.
By the end of the course, the students will be able to
• understand operating systems history, principles and structures;
• interact with operating systems through system calls and Application Programming Interface;
• understand process and thread management including process/thread operations, scheduling,
communications and synchronization;
• understand memory management including main memory and virtual memory allocation, mapping
and replacement;
• understand common input/output management, particularly storage management;
• understand file systems organization and implementation.

2. Computer Communications and Networks
UVic corresponding course: CSC 361 Computer Communications and Networks
The course objectives are to help students gain a general understanding of the principles and concepts
governing the operations of computer networks and to provide them with the opportunity to become skilled
in implementing and using communication protocols.
By the end of the course, the students will be able to
• use Wireshark to capture and analyze Internet traffic,
• use socket programming to implement/analyze an application-level protocol,
• develop programs to analyze a traffic trace file's structure and statistical features,
• understand TCP behaviour and identify TCP anomalies,
• config and test virtual routing devices, and
• test network performance using tools such as ping and traceroute.

3. Programming Languages
UVic corresponding course: CSC 330 Programming Languages
This course introduces fundamental concepts in computer programming languages, their design, syntax,
semantics, pragmatics and applications. Students will be exposed to (and will write programs using) very
different approaches towards expressing computation. Contrasting programming languages will be used for
assignments (Haskell, Rust, Javascript) that provide experience with different programming paradigms.
By the end of the course, the students will, among other learning outcomes, be able to
• summarize the evolution of programming languages by showing how we have arrived at paradigms
available to us today;
• compare and contrast the compiled and interpreted execution models;
• explain the value of declaration models;
• identify and describe the property of variables given a particular programming paradigm;
• demonstrate different forms of binding, visibility, scoping and lifetime management of variables;
• defend the importance of abstraction mechanisms made available by programming languages;
• justify the philosophy of object-oriented design and concepts of encapsulation, abstraction,
inheritance and polymorphism;
• design, code, test and debug programs using the object-oriented paradigm in a language other than
Java or C#;
• describe how iterators access the elements of a container;
• outline the strengths and weaknesses of the functional programming paradigm;
• design, code, test and debug programs using the functional paradigm;
• describe the steps and algorithms used by language translators;
• recognize the underlying formal models use to define a language through regular expressions and
grammars;
• evaluate languages with regard to typing.

4. Software Development Methods
UVic corresponding course: SENG 365 Software Systems Development.
Upon successful completion of the course, students will be able to
• describe the importance/impact of bad/good interface design;
• identify the potential human factor elements in a design;
• identify the representative users of a design and discuss who else could be impacted by this design
• identify the standard software architecture of a given high-level design;
• select and use an appropriate design paradigm to design a simple software system and explain how
system design principles have been applied in this design;
• discuss factors other than computational efficiency that influence the choice of algorithms, such as
programming time, maintainability, and the use of application-specific patterns in the input data;
• compare and contrast the different types and levels of testing (regression, unit, integration, systems,
and acceptance);
• describe techniques for creating a test plan and generating test cases;
• employ the fundamental principles of test-driven development methods and explain the role of
automated testing in these methods;
• undertake, as part of a team activity, a code review of a medium-size code segment;
• describe the role that tools can play in the validation of software;
• automate testing in a small software project;
• understand the use of Continuous Integration systems as a ground-truth for the state of the team’s
shared code (build and test success);
• describe the issues that are important in selecting a set of tools for the development of a particular
software system, including tools for requirements tracking, design modeling, implementation, build
automation, and testing;
• propose and delegate necessary roles and responsibilities in a software development team; and
• facilitate through involvement in a team project, the central elements of team building, establishing
healthy team culture, and team management including creating and executing a teamwork plan.

5. Human-centered Computing
UVic corresponding course: SENG 310 Human Computer Interaction
In this course, students will be introduced to the three main phases of HCI work: (a) understanding people,
(b) developing prototypes and (c) evaluation. More specifically, students will focus on understanding and
applying the human-centred design process. This course is not about developing technically robust software
systems, but instead will require students to develop an understanding of people’s everyday interactions
with computer technology and apply that understanding to critically reflect upon and suggest new ways to
improve or enhance human-computer interactions.
At the end of the course, students will be able to
• define foundational concepts in human-centred design and be able to differentiate between
different approaches and methods that can be considered when designing, implementing, and
evaluating a prototype computer-based interface;
• identify the goals, requirements, users, stakeholders, ethical considerations, context, and desired
outcomes of a design situation;
• apply design principles to design and develop an interactive prototype using appropriate rapid
prototyping tools and techniques, such as sketching, journey maps, storyboarding, and video
prototyping;
• plan and conduct an evaluation to address a user research problem, including the selection of an
appropriate evaluation technique and a critical assessment of the chosen method;
• as a team, critically analyze and synthesize findings to document and present the results from a
range of evaluation techniques such as controlled experiments, questionnaires, video evaluations,
field studies, and analytically based evaluations;
• synthesize diverse perspectives within a team to collaboratively define, design, and evaluate an
interactive prototype, and articulate the group's rationale for key design decisions.

6. Data Systems
UVic corresponding course: CSC 370: Database Systems
The objective of the course is to present an introduction to database management systems (DBMS), with an
emphasis on how to organize, maintain and retrieve--efficiently, and effectively--information from a DBMS.
By the end of this course, students will be able to
Database Design
• describe real-world domains in terms of data models (e.g., ER diagrams, relational
schemas);
• apply normalization and schema refinement techniques to design robust databases;
Data Analysis
• formulate and execute queries to extract, manipulate, and analyze data using query
languages (e.g., SQL);
• translate real-world questions into formal database queries and interpret results correctly;
Concurrency and Robustness
• explain how a DBMS handles concurrent access and transactions;
• demonstrate understanding of isolation levels, deadlocks, and recovery from system
failures;
Query Evaluation and Optimization
• explain how a DBMS parses, plans, and executes queries;
• compare different query execution strategies and evaluate their efficiency;
• apply query optimization techniques (e.g., use of indexes, join strategies, cost-based
optimization);
Efficiency and Scalability
• describe how databases store and index large volumes of data;
• evaluate query performance and identify bottlenecks;
• understand trade-offs in scaling databases to support large applications.

7. Artificial Intelligence and Machine Learning
UVic corresponding course: CSC 321 Course outline unavailable. (Placeholder CSC 421 Intro to AI)
By the end of the course, the students will have learned to
• understand the abstraction of agents as a framework for understanding AI concepts, as well as
integrating the various concepts and ideas learned during the course into working systems. For
example:
o mapping agent frameworks to specific problems,
o developing example systems to solve problems given in a specification;
• formulate various structured problems as search problems and be familiar with the variety of
algorithms and associated trade-offs that can be used to solve them. For example:
o leveraging structure in Constraint Satisfaction Problems (CSP) for efficiency,
o constructing multiple algorithmic solutions in the same theme to solve the same problem,
and understanding the trade-offs of these solutions;
• represent facts and knowledge using logic and understand the principles behind inference systems.
For example:
o converting a given specification into a given logic notation,
o developing a parser and basic inference system for this notation,
o using more advanced inference systems to solve a problem;
• be able to communicate about and structure various problems that feature uncertainty using
probabilities and probabilistic reasoning. For example:
o construct a probabilistic problem from scratch and then reason about outcomes,
o chart the change in belief over drawn samples using different probabilistic tools,
o reason about how AI agents can use this information to update their beliefs when solving
problems;
• be familiar with the basic terminology and development of machine learning techniques. For
example:
o using data to train effective algorithms,
o investigating measures of success/failure regarding trained models;
• be able to think critically about the ethical and safety implications of building systems using AI
technologies. For example:
o reason about the ethical implications of particular AI usage choices,
o map potential safety requirements/concerns to AI deployment scenarios,
o map ethical frameworks to dilemmas in AI development and deployment.

8. Graphics
UVic corresponding course: CSC 305 Intro to Computer Graphics
This course is an introduction to the field of computer graphics and its three main branches: modelling,
animation, and rendering. The course covers both theoretical and applied concepts such as transformations,
raster graphics with modern OpenGL, data structures for graphics, rendering algorithms, and computer
animation algorithms.
By the end of the course, the student will understand
• the modern real-time graphics pipeline;
• the transformations used in the graphics pipeline;
• projections, projection matrices, and their derivations;
• the development of shader-based rendering methods to implement the real-time graphics pipeline;
• texturing and UV mapping;
• hierarchical transformation modelling and developing animated linked transformations;
• both real-time and offline ray tracing and ray marching methods for high-fidelity rendering.

9. Computer Science Theory
UVic corresponding course: CSC 320 Foundations of Computer Science
By successfully completing the course, the student will be able to
• understand and analyze when it is possible to solve a problem computationally,
• understand and prove when a problem is undecidable,
• understand and illustrate how limitations on computational resources limit the class of problems
that can be solved,
• understand and apply models of computation for different problems in the Chomsky hierarchy,
• characterize and analyze computational problems that are tractable,
• characterize and prove computational problems that are intractable,
• characterize the class of problems solvable in a model,
• understand what it means for models of computation to be equivalent,
• understand and apply reductions to prove intractability and undecidability of problems,
• transform an automaton into a different equivalent representation, and vice versa.

https://uwaterloo.ca/centre-for-teachin ... ssessments

Bloom's Taxonomy Learning Activities and Assessments
Cognitive Domain
Bloom's Taxonomy: Cognitive Domain (PDF)

Cognitive Domain: intellectual skills and abilities required for learning, thinking critically and problem solving

Remember: Retain, recall and recognize knowledge

Understand: Translate and interpret knowledge

Apply: Apply knowledge to different situations

Analyze: Break down information to look at relationships

Evaluate: Make judgements based on evidence found

Create: Compile information to generate new solutions

similarly in research too, although focusing toward the discovery and creation side as well

Number	Source	Learning outcome
1	CS1	Design, implement, test, and debug a solution based on an abstract description of a problem.
2	CS1	Develop programs that use fundamental programming constructs (variables, types, expressions, assignment, basic I/O, conditional and iterative control structures, functions and parameter passing, structured decomposition)
3	CS1	Apply rigorous testing to validate the correctness of an implementation.
4	CS1	Describe the behaviour of a program through an examination of its source code.
5	CS1	Develop programs that use the different structured or compound data types provided in the language.
6	CS1	Describe the properties of good software design.
7	CS1	Describe the responsibility of a single programmer when working on a larger-scale project as part of a team.
8	CS1	Explain code of conduct and intellectual property relevant to programmers and software development.
9	Ethics	Articulate how computing technologes affect and must be designed considering social context, including social interactions, diversity of population including under-represented populations and the disabled, cultures, identities, and communities, as well as the role and impact of technology in democracy
10	Ethics	Analyze an argument to identify premises and conclusion and analyze (and avoid) basic logical fallacies in an argument.
11	Ethics	Evaluate how and why ethics is so important in computing and how it relates to cultural norms, values, and law.
12	Ethics	Identify, evaluate and address ethical issues that arise in software design, development practices, and software deployment, including software correctness, reliability and safety
13	Ethics	Describe, compare and select appropriate software license for a given project.
14	Ethics	Justify legal and ethical uses of copyrighted materials, including considering fair use and the many forms of plagiarism.
15	Ethics	Produce and evaluate concise and accurate technical documents following well-defined standards and formats.
16	Ethics	Develop and deliver an audience-aware, accessible, and organized formal presentation.
17	Ethics	Effectively, appropriately and collegially work and communicate as a member of a team, including applying conflict resolution techniques, effective communication, and inclusive and respectful interactions that value diversity of ideas.
18	Ethics	Understand the relevance and impact of computing history on recent events, present context, and possible future outcomes. Ideally from more than one cultural perspective.
19	Ethics	Define and distinguish equity, equality, diversity, inclusion, and accessibility.
20	Ethics	Describe the impact of power and privilege in the computing profession as it relates to culture, industry, products, and society, and factors that contribute to inequitable access, engagement, and achievement in computer science among marginalized groups.
21	HCI	Identify the different users of a design and their different needs and wants, both in terms of functionality and in terms of experience (functional and non-functional requirements)
22	HCI	Motivate, identify and argue for the value of considering human factors and knowledge about humans in the design of good interfaces,  considering the potential impacts of a design on society and relevant communities to address concerns such as sustainability, inclusivity, safety, security, privacy, harm, and disparate impact, and challenging developer's asumptions.
23	CS2	Develop programs that create simple classes and instantiate objects of those classes.
24	CS2	Describe the importance of abstraction and encapsulation in the design of programs.
25	CS2	Use a modern IDE to trace, step-through, and debug a program.
26	CS2	Recognize, analyze, and apply recursion to solve a problem.
27	CS2	Write reference-based and array-based implementations of basic algorithms and data structures
28	CS2	Describe the tradeoffs associated with a particular choice of data structure by reasoning about its efficiency in relation to a problem domain.
29	CS2	Describe the basic building blocks of computers and their role in the historical development of computer architecture.
30	Theory1	Given requirements for a real-world application, determine and evaluate data structures and algorithms in terms of suitability and impact on the environment and society.
31	Theory1	Define and give an example of an iterative algorithm, a recursive algorithm, as well as algorithm paradigms such as Brute-Force and Divide-and-Conquer.
32	Theory1	Define and use Big O notation (including Omega and Theta) to analyse time and space complexity of algorithms.
33	Theory1	Define and informally determine the foundational complexity class of simple algorithms.
34	Theory1	Perform empirical studies to determine the runtime complexity of algorithms.
35	Theory1	Describe in depth a prototypical example and its paradigm for graph and sorting algorithms.
36	Theory1	Graph algorithms (such as Shortest Path, Minimal spanning tree, transitive closure, and topological sort).
37	Theory1	Sorting algorithms (including those with O(n^2), O(n log n), and pseudo O(n) complexity).
38	Theory1	Informally describe common matching algorithms such as string matching, longest common subsequence matching, and regular expression matching.
39	Theory1	Define and describe the properties and associated operations of data structures such as sets, heaps, queues, graphs, and hash tables.
40	Theory2	Prove that the halting problem is undecidable and give an example of proving a problem is undecidable by reducing the halting problem to it.
41	Theory2	Given a real-world problem, design an appropriate automaton to address it.
42	Theory2	Define, compare and contrast, and give examples for each class of automata: Finite state, Pushdown, Linear Bounded, Turing Machine including universal Turing machine
43	Theory2	Explain at least one approach for addressing a computational problem whose algorithmic solution is exponential.
44	Theory2	Determine if a greedy approach leads to an optimal solution.
45	Theory2	Explain how invariants assist in proving the correctness of an algorithm as a formal model
46	Theory2	Describe an efficient string matching algorithm, longest common subsequence matching. and regular expression matching.
47	Theory2	Understand and explain in detail the following operations on data structures: collision avoidance and resolution in hash tables, and tree balance in binary search tree operations.
48	Theory2	Define the classes P and NP.
49	Theory2	Define, compare, and give examples of NP-complete and NP-hard problems.
50	Theory2	Prove that a problem is NP-complete by reducing it to a NP-complete problem.
51	Theory2	Convert between equivalently powerful notations for a language, e.g., DFAs, NFAs, and regular expressions; PDAs and CFGs.
52	Theory2	Use a pumping lemma to prove limitations of finite state and pushdown automata.
53	SW1	Learn how to work in a team, including communication, conflict resolution and collaboration
54	SW1	Use the mechanics and tools of SW teamwork such as version control and pull requests
55	SW1	Use version control
56	SW1	Write unit tests that establish robustness
57	SW1	Distinguish between program validation and verification. 
58	SW1	Use exception handling to make code robust.
59	SW1	Implement, document, and test a small component
60	SW2	Work in a team to build a multi module software project
61	SW2	Apply requirements modeling and elicitation to prepare a software specification.
62	SW2	Differentiate between different software architecture styles.
63	SW2	Select and use an appropriate design paradigm to design a simple software system and explain how system design principles have been applied in this design. 
64	SW2	Apply design principles and dependency models to analyze and re-design a flawed system
65	SW2	Trace requirements to design to implementation to tests of those requirements.
66	SW2	Conduct tradeoff analysis of software designs with respect to quality attributes.
67	SW2	Rewrite a simple program to remove common vulnerabilities, such as buffer overflows, integer overflows and race conditions.
68	SW2	Automate testing in a small software project. 
69	SW2	Undertake, as part of a team activity, a code review of a medium-size code segment. 

Sys1

* Understand and explain the history and evolution of computer architecture and organization.
* Describe and explain the binary data representation and format translation in computer systems.
* Describe and explain the classic von Neumann machine architecture, instruction set, and instruction cycle and pipelining in CPU.
* Describe and compare the performance of the memory hierarchy in current computer systems.
* Describe and compare the access methods and performance of input/output (I/O) devices.
* Write small programs in C to understand data representation and the interaction of CPU, memory and I/O devices.
* Describe and understand the principles and tradeoffs of the design, performance, reliability and security of computer systems.
* Understand the objectives and functions of modern operating systems.

Sys2

* Understand and explain the history and evolution of computer operating systems and structures.
* Describe and explain the principles and interaction of computer systems, operating systems and user applications with safety and protection.
* Describe and explain the scheduling, communication, synchronization and concurrency of processes and threads.
* Describe and compare the functionality and performance of cache, main memory and virtual memory.
* Describe and compare the management of different I/O devices, particularly storage devices.
* Describe and compare the design and implementation tradeoffs of file systems, directories and files.
* Write programs in C to understand and evaluate operating systems interfaces, CPU scheduling, memory allocation and filesystem implementation.
* Understand the objectives and functions of modern computer networks as an extension of operating systems.

https://csed.acm.org/wp-content/uploads ... Report.pdf

Professional dispositions – the whole person view
Professional dispositions are essential for not just succeeding in the workplace but also thriving as a
professional over the long run. The dispositions identified by multiple CS2023 knowledge areas as
essential for computer science graduates include:
• Adaptable, as the discipline is continually evolving;
• Collaborative, as most real-world applications are team efforts;
• Inventive in order to devise new solutions and apply existing solutions to new contexts;
• Meticulous to ensure the correctness and completeness of solutions;
• Persistent, since computational problem-solving is an iterative process;
• Proactive to anticipate issues pertaining to usability, security, ethics, etc.;
• Responsible in all aspects of a solution including design, implementation, and maintenance;
• Self-directed, as commitment to life-long learning is required due to rapid evolution of the
discipline.
These characteristics change in importance over the career of a graduate: some characteristics are
more important during early career while others are essential for success over the long run [4].
Moreover, given the dynamic nature of computer science, the desirable characteristics of computer
science graduates will also continue to evolve.

Networking and Communication (NC)

Preamble

Networking and communication play a central role in interconnected computer systems that are
transforming the daily lives of billions of people. The public Internet provides connectivity for
networked applications that serve ever-increasing numbers of individuals and organizations
around the world. Complementing the public sector, major proprietary networks leverage their
global footprints to support cost-effective distributed computing, storage, and content delivery.
Advances in satellite networks expand connectivity to rural areas. Device-to-device
communication underlies the emerging Internet of things.

This knowledge area deals with key concepts in networking and communication, as well as their
representative instantiations in the Internet and other computer networks. Beside the basic
principles of switching and layering, the area at its core provides knowledge on naming,
addressing, reliability, error control, flow control, congestion control, domain hierarchy, routing,
forwarding, modulation, encoding, framing, and access control. The area also covers knowledge
units in network security and mobility, such as security threats, countermeasures, device-todevice communication, and multihop wireless networking. In addition to the fundamental
principles, the area includes their specific realization in the Internet as well as hands-on skills in
implementation of networking and communication concepts. Finally, the area comprises emerging
topics such as network virtualization and quantum networking.

As the main learning outcome, learners develop a thorough understanding of the role and
operation of networking and communication in networked computer systems. They learn how
network structure and communication protocols affect behavior of distributed applications. The
area educates on not only key principles but also their specific instantiations in the Internet and
equips the student with hands-on implementation skills. While computer-system, networking, and
communication technologies are advancing at a fast pace, the gained fundamental knowledge
enables the student to readily apply the concepts in new technological settings.

Operating Systems (OS)

Preamble

Operating system is the collection of services needed to safely interface the hardware with
applications. Core topics focus on the mechanisms and policies needed to virtualize
computation, memory, and I/O. Overarching themes that are reused at many levels in
computer systems are well illustrated in operating systems (e.g. polling vs interrupts, caching,
flexibility costs overhead, similar scheduling approaches to processes, page replacement, etc.).
OS should focus on how those concepts apply in other areas of CS - trust boundaries,
concurrency, persistence, safe extensibility.

Operating systems remains an important Computer Science Knowledge Area in spite of how OS
functions may be redistributed into computer architecture or specialized platforms. A CS
student needs to have a clear mental model of how a pipelined instruction executes to how data
scope impacts memory location. Students can apply basic OS knowledge to domain-specific
architectures (machine learning with GPUs or other parallelized systems, mobile devices,
embedded systems, etc.). Since all software must leverage operating systems services,
students can reason about the efficiency, required overhead and the tradeoffs inherent to any
application or code implementation. The study of basic OS algorithms and approaches provides
a context against which students can evaluate more advanced methods. Without an
understanding of sandboxing, how programs are loaded into processes, and execution,
students are at a disadvantage when understanding or evaluating vulnerabilities to vectors of
attack.

12 Course Model

Please make sure CS core is covered no matter the choice of electives:

1. CS I (SDF, SEP)
2. CS II (SDF, AL, DM, SEP, Generic KA)
3. Math and Statistical Foundations (MSF)
4. Algorithms (AL, AI, SEC, SEP)
5. Introduction to Systems (SF, OS, AR, NC)
6. Programming Languages (FPL, AL, PDC, SEP)
7. Software Engineering (SE, HCI, GIT, PDC, SPD, DM, SEP)
8. Two from Systems electives:
   1. Operating Systems (OS, PDC)
   2. Computer Architecture (AR)
   3. Parallel and Distributed Computing (PDC)
   4. Networking (NC, SEC, SEP)
   5. Databases (DM, SEP)
9. Two electives from Applications:
   1. Artificial Intelligence (AI, SPD, SEP)
   2. Graphics (GIT, HCI, SEP)
   3. Application Security (SEC, SEP)
   4. Human-Centered Design (HCI, GIT, SEP)
10. Capstone (SE, SEP)

The capstone course is expected to provide the opportunity to cover any CS core topics not covered elsewhere in the curriculum.

pan wrote:knowledge: how computer works

skill: how to use computer to solve real-world problems

value: how computer enriches human beings and society

Date: August 16th
Time: 10:00am
Location: ECS 660

By: Alison Clear, Associate Professor, Eastern Institute of Technology, Auckland, Aotearoa/New Zealand
Co-Chair ACM & IEEE-CS for Global Computing Curricula 2020: Paradigms Computing Education
Chair ACM SIGCSE, ACM Distinguished Educator

Talk abstract:

The field of computing has grown exponentially in recent years, with new technologies emerging at a rapid pace. The rapid emergence of Artificial Intelligence agents will change how we work. Therefore, the traditional methods of teaching computing may struggle to keep up with this rapid pace of innovation. To ensure that universities keep pace with this development it is essential to look at what, why and how we are teaching the computing professionals of the future. Our new students of the immediate future will demand and need a different approach to teaching and learning. We need to shift the focus of computing education from knowledge based education to competency based education.

The work force is changing too with new technologies being developed it seems like on a daily basis. Now is the time to engage the employers of our future graduates and discuss the needs of the industry which our graduates will enter. What technical skills do they require and just as important what skills and dispositions will they need for future employment? It is important to address these questions in conjunction with industry before we redesign our under-graduate computing degree programs.

This talk will present an approach to teaching and learning by incorporating competency-based pedagogy, combining knowledge skills and dispositions in context to meet the needs of current and future computing students and their future employers. A combined landscape of computing knowledge and skills which covers all the areas of “computing” will be presented. It will also discuss engaging with industry to advise and direct their perspectives of new employees technical skills that will guide under graduate degree program curriculum.

“If everyone is moving forward together, then success takes care of itself.” Henry Ford

Alison Clear: Bio

Alison Clear is an Adjunct Associate Professor of the Eastern Institute of Technology. She has an extensive
academic and professional career that has involved academic leadership in research, scholarship, teaching and
curriculum development nationally and internationally and an extensive publication record in national and
international conferences and journals in computing and information technology. Her research interests include
Computing curriculum development, Women and Computing, ICT in developing countries, e-learning
implementation and the development of computing education. Alison is an invited international keynote speaker,
is currently the Chair of ACM Special Interest Group in Computer Science Education has been a member of the
international ACM Educational Council, member, currently Board member of the ACM Special Interest Group on
Computers and Society, Fellow of the Institute of Information Technology Professionals (IITP) and Fellow of the
Computing and Information Technology Research and Education in New Zealand (CITRENZ) and a
Distinguished Educator of ACM. In 2020 she received the ACM SIGCSE award for Lifetime Service to Computer
Science education. She recently led an international research project, Computing Curriculum 2020 (CC2020,) of
50 people from 22 countries to redefine the computing curricula for 2020 forward.

Changes since CS 2013: Compared to the 2013 curricula, the knowledge area broadens its core tier-1 focus from the introduction and networked applications to include reliability support, routing, forwarding, and single-hop communication. Due to the enhanced core, learners acquire a deeper understanding of the impact that networking and communication have on behavior of distributed applications. Reflecting the increased importance of network security, the area adds a respective knowledge unit as a new elective. To track the advancing frontiers in networking and communication knowledge, the area replaces the elective unit on social networking with a new elective unit on emerging topics, such as middleboxes, virtualization, and quantum networking. Other changes consist of redistributing all topics from the old unit on resource allocation among other units, in order to resolve the unnecessary overlap between the knowledge units in the 2013 curricula.

Knowledge Areas
Knowledge Areas planned for CS2023:

Algorithmic Foundations (AL)
Architecture and Organization (AR)
Artificial Intelligence (AI)
Data Management (DM)
Foundations of Programming Languages (FPL)
Graphics and Interactive Techniques (GIT)
Human-Computer Interaction (HCI)
Mathematical and Statistical Foundations (MSF)
Networking and Communication (NC)
Operating Systems (OS)
Parallel and Distributed Computing (PDC)
Security (SEC)
Society, Ethics and Professionalism (SEP)
Software Development Fundamentals (SDF)
Software Engineering (SE)
Specialized Platform Development (SPD)
Systems Fundamentals (SF)

* Decompose a real-world problem into sub-problems that can be iteratively refined and solved individually, or in teams.
* Develop a software system to solve a real-world problem.
* Design, evaluate, validate, and justify a solution that adheres to given or derived requirements by: adapting from useful algorithms, data structures, and code from existing solutions; considering trade-offs in quality attributes (e.g., , time, space, security); and applying best practices.
* Construct a formal argument and formulate logically-sound proofs, both to show correctness and prove the space and time complexity of an approach.
* Independently acquire knowledge of unfamiliar technologies, languages, frameworks, and architectures.
* Implement a program using modern team-based development practices.
* Identify the different layers of abstraction in a system and the interactions within the layers with respect to how data and execution are represented in that system.

Computer Science Curricula 2013

Curriculum Guidelines for Undergraduate Degree Programs in Computer Science

December 20, 2013

The Joint Task Force on Computing Curricula Association for Computing Machinery (ACM) IEEE Computer Society

Knowledge Areas
The CS2013 Body of Knowledge is organized into a set of 18 Knowledge Areas (KAs), corresponding to topical areas of study in computing. The Knowledge Areas are:
● AL - Algorithms and Complexity
● AR - Architecture and Organization
● CN - Computational Science
● DS - Discrete Structures
● GV - Graphics and Visualization
● HCI - Human-Computer Interaction
● IAS - Information Assurance and Security
● IM - Information Management
● IS - Intelligent Systems
● NC - Networking and Communications
● OS - Operating Systems
● PBD - Platform-based Development
● PD - Parallel and Distributed Computing
● PL - Programming Languages
● SDF - Software Development Fundamentals
● SE - Software Engineering
● SF - Systems Fundamentals
● SP - Social Issues and Professional Practice

csc major

and honors

CSC226 Algorithms and Data Structures II

Existing Calendar Entry

Advanced techniques for design, analysis, and implementation of algorithms and data structures with an introduction to algorithm engineering. Algorithmic design paradigms: greedy, divide-and-conquer, dynamic programming, backtracking, branch and bound. Advanced Analysis techniques, such as amortization. Advanced data structures: hashing, disjoint sets. Advanced graph algorithms: network flow, connectivity, minimum spanning trees, shortest paths. Mathematical tools: graphs and digraphs, graph properties, planar graphs, networks; discrete probability, counting techniques, recurrences.

Prerequisites

CSC225

Current Topics

• intro, big-O, RAM model review
• review quicksort, selection
• discrete probability and randomized algorithms
• hashing
• union-find problem [1.5]
• MST Kruskal [4.3]
• MST Prim's alg [4.3]
• MST Bellman-Ford
• shortest paths [4.4]
• dynamic programming, LCS
• strings, KMP algorithm, tries [5]
• network flow [6]

Proposed Learning Outcomes (Spring 2022)

General Outcomes

• Describe fundamental algorithm design paradigms (Divide and Conquer, Greedy, Dynamic Programming) and advanced data structures (Weighted Graphs, Union-Find).
• Apply mathematical techniques and tools (such as recurrence relations, counting, graph theory) to analyze the running times of algorithms and reason about their correctness.
• Compare and choose the most appropriate design paradigm and data structure(s) to solve a given problem by studying its structure and resemblance to previously studied problems.
• Implement correctly the best solution to a given problem obtained after the design and analysis stage.

Weighted Graphs

• Recall graph terminology arc, in-degree, out-degree, path, directed path, cycle, directed cycle, connected, strongly connected, etc.
• Define and identify a spanning tree and spanning forest
• Develop intuition that weighted graphs can be used to model many types of relations (ie. maps, social and physical networks, biological structures, etc.)
• Implement weighted graph representations (i.e. adjacency list, adjacency matrix) with related operations
• Analyze abstract data type Weighted Graph algorithms in terms of space/time complexity

Minimum Spanning Trees

• Explain how a Heap of n elements can be constructed in O(n) time (NOTE to discuss with rest of group: if we push this to 225, push transitive closure to 226)
• Define the abstract data type Union-Find (i.e. make, union, find)
• Trace the following algorithms on a given weighted graph: Kruskal, Dijkstra/Prim, Boruvka
• Prove the correctness of two of Kruskal, Dijkstra/Prim, Boruvka
• Identify examples of Greedy algorithms that solve other problems; explain why they are greedy

Shortest Paths

• Define and identify a shortest path in a weighted graph
• Trace the following shortest path algorithms on a given weighted graph: Dijkstra's, Bellman-Ford
• Prove the correctness of Dijkstra's algorithm
• Identify examples of Dynamic Programming algorithms that solve other problems; explain why they are Dynamic Programming (Longest Common Subsequence, Knapsack, Coins-in-a-Line)
• Define and apply transitive closure relations to directed graphs
• Define algorithm to determine transitive closure on a directed graph
• Trace the all-pairs shortest path algorithm, Floyd-Warshall

Network Flow

• Define Network Flow and accompanying definitions and terminology (i.e. source, sink, capacities, flow, etc.)
• Construct a Residual Graph given a Network Flow
• Define and discover an augmenting path in a Network Flow
• Define maxflow and mincut
• Prove relationship between maxflow and mincut
• Trace the following maxflow algorithms: Ford-Fulkerson, Edmonds-Karp
• Analyze Edmonds-Karp algorithm in terms of time complexity

Advanced Sorting and Selection

• Recall the Quicksort algorithm
• Apply introductory probability techniques to average-case running time analysis
• Explain why the Quicksort average case running time differs from the worst case running time
• Apply the Quicksort algorithm to selection, i.e. Quickselect
• Explain the linear selection algorithm and analyze its running time
• Understand the concept of randomization in algorithms
• Apply randomization to the Quicksort and Quickselect algorithms and analyze their running times

Hashing

• Recall the concept of a Hash table and Hash function
• Recall the implementation of hash insert and search (i.e. collision, open-addressing, closed (eg. chaining))
• Implement delete from a Hash table
• Define load factor and analyze the runtime of Hash table operations
• Explain and apply amortized algorithm analysis techniques

String Search

• Describe a Deterministic Finite Automata (DFA)
• Trace and analyze the following substring search algorithms: Knuth-Morris-Pratt (KMP with DFA), Rabin-Karp, Boyer-Moore (simplified version)

Optional Topics

• Define graph colouring and identify graphs that are two- and three-coloured
• Proof that a graph is two colourable, i.e. it does not contain an odd cycle
• Identify Euler and Hamilton graphs
• Define a planar graph
• Prove Kuratowski's theorem
• Define and apply Euler's formula
• Describe algorithms for planar graph isomorphism
• Discover examples of hard problems (intractability)
• Use backtracking, branch and bound and alpha - beta pruning

CSC225 Algorithms and Data Structures I

Existing Calendar Entry

Basic techniques for design, analysis, implementation of algorithms and data structures. Foundations: Random access machine model, time and space complexity, worst-case analysis, upper and lower bounds. Proof techniques for algorithm correctness. Basic data structures: stacks, queues, linked lists. Sorting: elementary sorting algorithms, mergesort, quicksort, priority queues. Searching: Binary search trees, balanced search trees, hash tables. Graphs: undirected and directed graphs, graph traversals and applications, topological sort. Algorithm design techniques: greedy, backtracking, divide and conquer.

Prerequisites

CSC115 or CSC116
MATH122

Current Topics

Algorithm Design and Analysis

• Algorithm design techniques
• Fundamental algorithm analysis
• Time and space complexity
• Asymptotic analysis
• Recursive analysis and recurrence relations
• Proof techniques
• Basic data structures: arrays, lists, stacks and queues

Searching and Sorting

• General purpose sorting algorithms, such as Heap sort, Insertion sort, Merge sort, Quick sort, and Selection sort
• Special purpose sorting algorithms, such as lexicographical sorting and Radix sort
• Priority Queues (including Heaps)
• Binary Search Trees
• Balanced Search Trees
• Graphs

Mathematical foundations

• Problem abstraction with graphs
• Data structures for graph representation
• Fundamental graph traversal algorithms and applications
• Connectivity and strong connectivity
• Topological sorting

Proposed Learning Outcomes (spring 2022)

• Explain the tradeoffs in data structure and algorithm design with respect to space/time complexity

Discrete math

• Apply combined identities, geometric sums, permutations, and combinations
• Explain the concept of the Pigeon Hole Principle

Pseudocode

• Express a simple algorithm in pseudo code
• Explain random access machine model – Determine the number of operations required to execute an algorithm through an analysis of pseudocode

Recursion

• Define recurrence relation for a given recursive algorithm
• Solve simple recurrence relations using substitution methods

Proofs

• Apply various proof techniques for algorithm correctness (i.e. proof by counterexample, direct proof, proof by contrapositive, proof by contradiction)
• Identification of the loop invariant by examining the pseudocode for an algorithm
• Apply proof by induction when analyzing algorithms and reasoning about their correctness (ie. loop invariant)

Asymptotic Analysis

• Define the concepts of problem size and running time
• Define the concept of asymptotic time complexity using (Big Oh, Big Omega, Big Thetha, Little Oh, Little Omega)
• Order functions by growth rate
• Explain why efficiency matters
• Compare/contrast time complexity measurements (best-case, average-case, or worst-case)
• Justify the time complexity of various algorithms (best-case, worst-case)

ADT review

• Recall and differentiate between stacks, queues, dequeues, lists
• Recall the impact of data structure choice on algorithm runtime
• Define the abstract data type Dictionary (i.e. Member, Insert, Delete operations)

Sorting

• Describe characteristics of sorting (in-place, stable sort)
• Recall definitions of partial and total orders
• Recall properties of relations (reflexive, symmetric, antisymmetric, transitive)
• Explain the comparison model of sorting and what correctness of comparison based sorting means
• Analyze the best-case and worst-case running time of Insertion Sort, Bubble Sort, Selection Sort
• Implement divide and conquer sorting algorithms (Merge Sort, Quicksort)
• Analyze best-case, worst-case running time of divide and conquer sorting algorithms (Merge Sort, Quicksort)
• Define the abstract data type Priority Queue (i.e. Member, Insert, DeleteMin/DeleteMax operations)
• Analyze the worst-case running time of Heapsort
• Explain why, in practice, Quicksort performs better than Heapsort
• Apply Pigeon Hole Principle to prove nlogn lower bound of comparison-based sorting algorithms
• Implement non-comparison sorting algorithms (Bucket Sort, Radix Sort)
• Analyze best-case, worst-case running time of non-comparison sorting algorithms (Bucket Sort, Radix Sort)

Trees

• Develop intuition that trees can be used to model many types of relations (ie. abstract syntax trees, hierarchies or organizations)
• Define tree nomenclature (e.g. root, node, interior points, leaf nodes, parent, children, height, rotted trees, forests)
• Prove tree properties (e.g. number of edges, number of edges in a forest with k components, or height of a balanced tree)
• Evaluate tree representations/algorithms in terms of space/time complexity (i.e. linked, arrays)
• Analyze and implement recursive and iterative tree traversal algorithms (i.e. pre-order/depth-first, in-order, post-order, level-order/breadth-first, Euler tour)
• Recall the abstract data type Dictionary/Map (i.e. search, insert operations)
• Recall the abstract data type Binary Search Tree (i.e. search, insert operations)
• Describe delete/remove operation for Dictionary/Map and Binary Search Tree
• Analyze the worst-case running time of Dictionary/Map and Binary Search Tree operations

Balanced Search Trees

• Define and identify a balanced search tree (at least 2 of the following covered: AVL, B-Trees, 2-3 Trees, Red-Black Trees)
• Analyze the worst-case running time of balanced search tree operations (search, insert, remove)
• Prove properties of balanced search trees (height, min/max leaves)
• Compare/contrast the runtime efficiency of operations in balanced and unbalanced trees

Graphs

• Develop intuition that graphs can be used to model many types of relations (ie. maps, social and physical networks, biological structures, etc.)
• Define graph nomenclature (e.g. undirected/directed graph, vertex, edge, etc.)
• Provide precise mathematical definitions of fundamental constructs from discrete mathematics, including: undirected/directed graph, vertex, edge, arc, degree, adjacent, incident, path, cycle, self-loop, directed acyclic graph (DAG), complete graph, subgraph, number of edges in a complete graph, sparse and dense graph, shortest path, transitive closure, connected, strongly-connected, and spanning tree.
• Implement graph representations (i.e. adjacency list, adjacency matrix) with related operations
• Analyze abstract data type Graph algorithms in terms of space/time complexity
• Implement iterative/recursive Graph traversal algorithms (i.e. preorder/depth-first (DFS), breadth-first (BFS))
• Analyze worst-case running time of Graph traversal algorithms (i.e. preorder/depth-first (DFS), breadth-first (BFS))
• Define spanning tree/spanning forest in relation to traversal algorithms
• Define and apply transitive closure relations to directed graphs
• Define algorithm to determine transitive closure on a directed graph
• Determine whether a graph is cycle-free using DFS – Implement and apply a topological sort on a directed graph