Contacts

Undergraduate Menu

Undergraduate Quicklinks

Course Details

01:198:344 - Design and Analysis of Computer Algorithms

  • Course Number: 01:198:344
  • Instructor: Arpita Biswas, Yongfeng Zhang, Mario Szegedy
  • Course Type: Undergraduate
  • Semester(s) Offered: Fall, Spring, Summer
  • Credits: 4
  • Description:

    To study a variety of useful and elegant algorithmic paradigms and learn how to analyze their complexity and correctness; by that experience to gain insight into principles and data-structures useful in algorithm design and develop algorithmic thinking skill.
  • Instructor Profile: Biswas, Arpita, Szegedy, Mario, Zhang, Yongfeng
  • Prerequisite Information:

    01:198:112; 01:198:206.

    - A grade below a "C" in a prerequisite course will not satisfy that prerequisite requirement.
  • Course Links: 01:198:112 - Data Structures, 01:198:206 - Introduction to Discrete Structures II
  • This course is a Pre-requisite for the Following Courses: 01:198:452 - Formal Languages and Automata
  • Topics:

    Methods for expressing and comparing the time and space complexity of algorithms. Algorithmic design paradigms: greedy, dynamic programming, and divide and conquer. Application of complexity analysis and algorithmic techniques to a variety of problems, including allocation, searching, sorting, scheduling, packing, and graph problems (including bipartite matching, shortest path, and minimum spanning tree). NP and P problems (knapsack, satisfiability, independent set, vertex cover). NP Completeness and Reductions. 
  • Exams: Short quizzes, midterm and final exam.
  • Learning Goals:
    • Computer Science majors ...
      • will be prepared to contribute to a rapidly changing field by acquiring a thorough grounding in the core principles and foundations of computer science (e.g., techniques of program design, creation, and testing; key aspects of computer hardware; algorithmic principles).
      • will acquire a deeper understanding on (elective) topics of more specialized interest, and be able to critically review, assess, and communicate current developments in the field.
      • will be prepared for the next step in their careers---whether pursuing computer science research, software engineering, or entrepreneurship---with the foundational knowledge and problem-solving skills needed to succeed in a rapidly evolving field.