Course Details
01:198:344 - Design and Analysis of Computer Algorithms
- Course Number: 01:198:344
- Instructor: Sepehr Assadi, Aaron Bernstein
- Course Type: Undergraduate
- Semester 1: Fall
- Semester 2: Spring
- Credits: 4
- Description:
To study a variety of useful algorithms and analyze their complexity; by that experience to gain insight into principles and data-structures useful in algorithm design.
- Syllabus: https://www.cs.rutgers.edu/~sa1497/courses/cs344-s21/course-syllabus.pdf
- Video Intro: https://www.cs.rutgers.edu/~sa1497/courses/cs344-s21/cs344-s21-intro.mp4
- Instructor Profile: Assadi, Sepehr, Bernstein, Aaron
- 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 complexity of algorithms: worst and average cases, lower bounds on algorithm classes, verification of correctness. Application of such analysis to variety of specific algorithms: searching, merging, sorting (including quick and heap internal and Fibonacci external sorts); graph problems (including connected components, shortest path, minimum spanning tree. and biconnected components); language problems (including string matching and parsing).
Consideration of a number of hard problems: knapsack, satisfiability, traveling salesman problems.
Development of NP-complete classification and its consequence.
Approximation algorithms. - Expected Work: Regular exercises, (about) 6 small programs
- Exams: Short quizzes, midterm and final exam (See Instructor's Class URL for more details)
- 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, for example, by having done a research project (for those headed to graduate school), a programming project (for those going into the software industry), or some sort of business plan (for those going into startups).
- Notes:
Informationa about Prof. Aaron Bernstein's sections:
Video Intro: https://www.youtube.com/watch?v=TNAjfOdZf4Y
