CS210{C,S,T,W}. Algorithm Design and Analysis

Prerequisites: introduction to computer science (any implementation of CS103 or CS112), discrete structures (CS106 or CS115)

Syllabus:

• Review of proof techniques
• Basic algorithmic analysis: Asymptotic analysis of upper and average complexity bounds; best, average, and worst case behaviors; big-O, little-o, omega, and theta notation; standard complexity classes; empirical measurements of performance; time and space tradeoffs in algorithms; using recurrence relations to analyze recursive algorithms
• Fundamental algorithmic strategies: Brute-force; greedy; divide-and-conquer; backtracking; branch-and-bound; heuristics; pattern matching and string/text algorithms; numerical approximation
• Fundamental data structures: Implementation strategies for graphs and trees; performance issues for data structures
• Graph and tree algorithms: Depth- and breadth-first traversals; shortest-path algorithms (Dijkstra's and Floyd's algorithms); transitive closure (Floyd's algorithm); minimum spanning tree (Prim's and Kruskal's algorithms); topological sort
• Automata theory: Finite-state machines; Turing machines; context-free grammars; uncomputable functions; the halting problem; implications of uncomputability
• Introduction to language translation: Comparison of interpreters and compilers; language translation phases; machine-dependent and machine-independent aspects of translation; language translation as a software engineering activity

Units covered:

DS3	Proof techniques	3	core hours (of 12)
DS5	Graphs and trees	4	core hours
PF2	Algorithms and problem-solving	3	core hours (of 6)
PF3	Fundamental data structures	3	core hours (of 14)
PL3	Introduction to language translation	2	core hours
AL1	Basic algorithmic analysis	2	core hours (of 4)
AL2	Algorithmic strategies	6	core hours
AL3	Fundamental computing algorithms	6	core hours (of 12)
AL5	Basic computability	6	core hours
AL6	The complexity classes P and NP	2	hours
AL7	Automata theory	2	hours
	Elective topics	1	hour

Notes:
The topic of algorithmic analysis is central to much of computer science. The thrust of this course is to explore and examine a range of algorithms that can be used to solve practical problems. Each algorithm possesses strengths and weaknesses. Moreover, the performance or any particular algorithm typically varies according to the size and nature of the input data. Students need a thorough understanding of the tools of analysis in order to select the right algorithm for the job.

Students are most receptive to the material presented in this course if they understand the connections between theory and practice. To this end, instructors should try to find ways to reinforce the theoretical topics through practical activity. It is also important for instructors to provide compelling demonstrations of the enormous differences in running time that can occur when algorithms have different complexity characteristics. The importance of complexity measures must be made real.

Algorithmic animation can be a powerful tool toward getting students to understand both the algorithms themselves and the associated complexity measures. Tools for creating graphical animations of classical algorithms are widely available on the web. These tools provide visible evidence of the complexity measures and thus reinforce the theoretical results.

It is also possible to take a more formal approach to this topic that focuses on formal specification of algorithms and proofs of correctness, possibly supported by appropriate specification and verification tools. A more informal approach, however, is likely to appeal to a wider spectrum of students.

Students who complete this course should be able to perform the following tasks:

• Explain the mathematical concepts used in describing the complexity of an algorithm.
• Select and apply algorithms appropriate to a particular situation.
• Employ one from a range of strategies leading to the design of algorithms to serve particular purposes.
• Explain the trade-offs that exist between a range of algorithms that possess the same functionality.

Online resources for CS210