CMPSC 465: Data Structure and Algorithms

Textbook Information

  • Introduction to the Design and Analysis of Algorithms
    Anany Levitin, 3rd Edition, Addison Wesley, 2012
    ISBN-13: 978-0132316811
    ISBN-10: 0132316811

Published Remarks

  • None

Hardware Requirements

  • None

Software Requirements

  • None

Proctored Exams

  • None

Course Description

Data structures and algorithms form a major component of any software system. When building such a system, a skilled computer scientist must make intelligent decisions about alternative techniques, choosing from existing data structures and algorithms or designing his/her own when necessary. This course emphasizes the development of data structures, design and analysis of algorithms. The goal is to learn algorithms for fundamental problems in computer science, to learn the data structures which support the efficient implementation of these algorithms, as well as to learn methods of analyzing the efficiency of algorithms.

Overview

This course will cover three major components including the algorithm analysis framework, a variety of algorithm design techniques, and the limitations of algorithm power.

Course Outline

Course Outline:

Module 1 – Course intro and a review of basic data structures Module 2 – Algorithm analysis framework – part 1 Module 3 – Algorithm analysis framework – part 2 Module 4 – Brute force and exhaustive search Module 5 – Decrease and conquer – part 1 Module 6 – Decrease and conquer – part 2 Module 7 – Divide and conquer Module 8 – Transform and conquer – part 1 Module 9 – Transform and conquer – part 2 Module 10 – Space and time tradeoff Module 11 – Dynamic programming Module 12 – Greedy method Module 13 – Iterative improvement – part 1 Module 14 – Iterative improvement – part 2 Module 15 – Algorithm limitations

Learning Objectives

Upon completion of the course, students will be able to:

  1. Identify key concepts of data structures and algorithms
  2. Master the algorithm analysis framework for algorithm performance analysis in terms of time and space complexity.
  3. Identify the principles of brute force and exhaustive search
  4. Identify the principles of decrease and conquer
  5. Identify the principles of divide and conquer
  6. Identify the principles of transform and conquer
  7. Identify the principles of space and time tradeoff
  8. Identify the principles of dynamic programming
  9. Identify the principles of greedy method
  10. Identify the principles of iterative improvement
  11. Exploring various algorithm design options to decide the best implementation strategy
  12. Describe the limitations of algorithm power

Outcomes

Upon completion of the course, students should possess the following skills:

  • Compare algorithms in terms of time and space efficiency
  • Understand the algorithm design patterns and apply them to solve existing/new problems, in particular, students should be able to
    • apply brute force and exhaustive search strategy to solve problems
    • apply decrease and conquer strategy to solve problems
    • apply divide and conquer strategy to solve problems
    • apply transform and conquer strategy to solve problems
    • apply space and time tradeoff strategy to solve problems
    • apply dynamic programming strategy to solve problems
    • apply greedy strategy to solve problems
    • apply iterative improvement strategy to solve problems
  • Analyze the limitations of algorithm power.

This course supports the following Software Engineering ABET outcomes:

(a) An ability to apply knowledge of computing and mathematics appropriate to the program’s student outcomes and to the discipline. 2018-07-12_20-28-54.png (b) An ability to analyze a problem, and identify and define the computing requirements appropriate to its solution. (j) An ability to apply mathematical foundations, algorithmic principles, and computer science theory in the modeling and design of computer-based systems in a way that demonstrates comprehension of the tradeoffs involved in design choices.

Textbook and References

  • Text:Introduction to the Design and Analysis of Algorithms Anany Levitin, 3rd Edition, Addison Wesley, 2012 ISBN-13: 978-0132316811 ISBN-10: 0132316811

Technical Specifications

For this course we recommend the minimum World Campus technical requirements listed below:

Operating  System Modern distributions of Linux (e.g. Ubuntu 18.04 LTS (Bionic Beaver)) Windows Vista, Windows 7, Windows 8*, Windows 10, Mac OS X 10.5. or higher *Windows 8 support excludes the tablet only RT version
Memory 2GB of RAM
Hard Drive Space 20 GB free disk space
Browser We recommend the latest Canvas-supported version of Firefox or Chrome.
Plug-ins Adobe Reader [Download from Adobe (Links to an external site.)] Flash Player [Download from Adobe (Links to an external site.)] Apple QuickTime [Download from Apple (Links to an external site.)]
Additional Software Microsoft Office (2007 or later)
Internet Connection Broadband (cable or DSL) connection required
Printer Access to a graphics-capable printer
DVD-ROM Required
Sound Card, Microphone, and Speakers Required
Monitor Capable of at least 1024×768 resolution

If you need technical assistance at any point during the course, please contact the  HelpDesk (Links to an external site.). For registration, advising, disability services, help with materials, exams, general problem solving, visit  World Campus Student Services (Links to an external site.)!

Course Requirements and Grading

Grading Policy

Grading is based on midterm exams, quizzes, lab assignments, and course projects. The following weights are assigned to the different assessed components of the course:

Category Percentage
Assignments 15%
Projects 20%
Quizzes 10%
Participation 2%
KS Essays 3%
Exam 1 15%
Exam 2 15%
Final Exam 20%

  Assignments:

  • An assignment consists of a set of problems to be solved using the learning points covered in class.
  • All algorithmic solutions should be written in pseudo-code (the pseudo-code standard for this course will be covered in module 1).
  • Assignments are given and collected on a weekly basis. They are assigned on the Monday of each week and are due by Sunday (11:59 pm, US Eastern time) of the same week.
  • Assignments may be submitted up to 24 hours late (next Monday11:59 pm, US Eastern time)  for up to 75% credit. Beyond that, no credit will be given.

Projects:

  • All programming projects should be developed using C++.
  • All programs must compile; programs that do not compile will receive a drastically reduced grade. Make sure you provide adequate test cases to indicate the correctness and robustness of your program.
  • Execution outputs of your program on test data must be produced and pasted as comments at the end of your main source code file. You may refer to the Project Documentation and Submission Guidelines for details.
  • Grading Rubric of Projects
    • 40% – there exists a submission, otherwise, no points will be given.
    • 20% – the program has reasonable design and logic.
    • 40% – the program passes all test cases in the project instruction. If the program does not compile, 40% will be taken off and all test cases are defaulted zero. One test case is worth 40%thenumberoftestcases.
  • There will be seven projects in total.

Quizzes: Quizzes are short and designed to make sure your knowledge on the current topic is sufficient. Participation: Students are encouraged to use the participation forum on Canvas to post questions/comments for the course, as well as to help answer classmates’ questions. Exams: Each exam will cover one of the overarching topics of the course with minor (if any) overlap.

  • Exam 1 will cover module 1 ~ module 5
  • Exam 2 will cover module 6 ~ module 10
  • The final exam is comprehensive.

Grade Assignments

Assessments are based on 100 points with final letter grades being assigned as follows:

A A- B+ B B- C+ C D F
100-93 92-90 89-87 86-83 82-80 79-75 74-70 69-60 59-0