CSCI 4041: Algorithms and Data Structures

Overall Description

4041 is a required course for computer science and computer engineering majors. It is a useful course for other students who desire to learn some core material in computing. We expect computer science and computer engineering students to take 4041 in their junior year. 4041 builds upon material from 2011 (Discrete Structures) and 1902 (CS II), and is a prerequisite for many CSci elective courses. Upon successfully completing this course students should know many fundamental algorithms and data structures commonly used in computer science. Moreover, they should be able to use these algorithms and data structures both in programming, and in problem analysis.

Catalog Description

Rigorous analysis of algorithms and their implementation. Topics such as algorithm analysis, sorting algorithms, binary trees, heaps, priority queues, heapsort, balanced binary search trees, AVL trees, hash tables and hashing,graphs, graph traversal, single source shortest path, minimum cost spanning trees.

Content

Why this Class is Important and its Role in the Curriculum

Familiarity with fundamental algorithms, and the ability to use them to analyze problems and to implement solutions, is crucial in many computer science applications.

Prerequisites and Rationale

4041 has 2011 (Discrete Structures) and 1902 (CS II) as prerequisites. In 2011 students should have become adept with tools such as various proof and analysis techniques, and have obtained an introduction to topics such as big-O notation, trees, and graphs. 4041 builds on this knowledge. Part of 4041 will be a brief review of these concepts and tools, but the course will assume that students already have some knowledge of them.

In 1902 students learn some basic data structures (e.g., queues and stacks) and algorithms (e.g., binary search), as well as Java programming. 4041 will briefly review the algorithms and data structures, but will assume that students already have some knowledge of them, as well as good Java programming skills.

Courses that have 4041 as a Prerequisite

Numerous elective classes have 4041 as a prerequisite. Examples include 4107/5107 (Graphics), 5115 (Human-Computer Interaction), 5403 (Computational Complexity), 5421 (Advanced Algorithms and Data Structures), 5451 (Parallel Algorithms), and 4707/5707 (Databases). In all of these classes familiarity with algorithms and data structures and analysis tools are important. For example, the parallel algorithms class requires the ability to modify algorithms to run on parallel machines, and the ability to obtain time bounds for parallel algorithms.

Class Format

4 credits, 3 large class + 1 recitation hour per week. Recitation can be used for problem solving and review, or more in-depth discussion of topics and examples given in the large class. Since many students struggle with topics like analyzing algorithms, identifying what algorithms/data structures are appropriate to use in given situations, etc., the practice given in recitation will be valuable.

Probable Text, If Any

Introduction to Algorithms, 2nd ed., Cormen, Leiserson, Rivest, and Stein. McGraw-Hill, 2001.

Outcomes

1. For each of the data structures (e.g., graphs), or techniques (e.g., big-O analysis, greedy algorithms) discussed in class, the student should be able to:
   1. define the basic terminology and use it correctly.
   2. give an explanation of why it is important.
   3. provide and discuss specific CSci examples of its use.
   4. be able to identify its important characteristics, as well as any variants or special cases.
   5. perform the basic operations associated with it.
   6. use it, when applicable, to analyze and solve problems.
2. For each of the algorithms discussed in class, the student should be able to:
   1. explain the algorithm's purpose, key steps, major characteristics, and what types of problems it’s applicable to; and given input, be able to trace through the workings of the algorithm.
   2. be able to analyze the time and space requirements of the algorithm (including variants or special cases of the algorithm).
   3. be able to analyze correctness of a purported algorithm.
   4. be able to explain general features of particular types of algorithms (e.g., greedy algorithms).
3. Students should also have the following additional analysis, problem solving, and presentation skills. Given a problem, students should be able to:
   1. identify which structures, algorithms, and/or techniques could be useful in analyzing or solving the problem, and why; and be able to modify or specialize structures, algorithms, or techniques to make them applicable to problems that are not amenable to straightforward use of the structure, algorithm or technique.
   2. present a clear, concise, logically accurate, and rigorous solution.
   3. tell whether a purported solution or analysis is accurate.
   4. if appropriate, be able to design and implement a coded solution.