CSC 331 - Algorithm Analysis

From Metaverse

Contents 1 Semester Hours 2 Course Coordinator 3 Catalog Description 4 Textbook 4.1 2006 Textbook 5 Course Goals 6 Prerequisites by Topic 7 Major Topics Covered in the Course 8 Learning Outcomes (Cross-Referenced with Program Outcomes) 9 Laboratory Projects 9.1 2006 Laboratory Projects 10 Estimate CSAB Category Content 11 Oral and Written Communication 11.1 2006 Oral and Written Communication 12 Social and Ethical Issues 13 Theoretical Content 14 Problem Analysis 15 Solution Design 16 Course Assessment 16.1 2008 16.1.1 Items to be assessed, assessement mechanism, and success criteria 16.1.2 Assessment data and analysis 16.1.3 Suggestions for next offering 16.2 2007 16.2.1 Proposed changes from last offering 16.2.2 2007 Items to be assessed, assessement mechanism, and success criteria 16.2.3 Assessment data and analysis 16.2.4 Proposed changes for 2008 16.2.5 Proposed changes for 2007 16.3 2006 16.3.1 2006 Proposed changes 16.3.2 2006 Items to be assessed, ... 16.3.3 Assessment data and analysis

Semester Hours

4sh

Course Coordinator

Joel Hollingsworth

Catalog Description

Students analyze structures and appropriate algorithms for sorting, merging, and searching in the contexts of mass storage devices, internal main memory, and Artificial Intelligence (AI) applications. Topics include graph algorithms, dynamic storage allocation and garbage collection. Prerequisites: CSC 230 and MTH 206. Offered spring.

Textbook

Algorithms
Dasgupta, Papadimitriou, and Vazirani
McGraw Holl, 2007, ISBN 978-0-07-352340-8

2006 Textbook

Introduction to Algortihms (Second Edition)
Cormen, Leiserson, Rivest, and Stein
McGraw Hill, 2002, ISBN 978-0262032933

Course Goals

Explore the enterprise of the development and design of efficient algorithms using a high-level language.

Prerequisites by Topic

DS1. Functions, relations, and sets
DS4. Basics of counting
DS5. Graphs and Trees
DS6. Discrete probability
PF1. Fundamental programming constructs
PF3. Fundamental Data Structures

Major Topics Covered in the Course

DS4. Basics of Counting
DS5. Graphs and Trees
PF3. Fundamental Data Structures
PF4. Recursion
AL1. Basic Algorithm Analysis
AL2. Algorithmic strategies
AL3. Fundamental computing algorithms
AL8. Advanced algorithmic analysis

Learning Outcomes (Cross-Referenced with Program Outcomes)

• Student will have a strong understanding of basic algorithmic concepts, including: Big-O, divide-and-conquer, greedy, dynamic programming. [Program Outcome 5 and 8]
• Students will understand graph data structures and a number of graph algorithms. [Program Outcome 5]
• Students will understand the necessary mathematical rigor need to discuss algorithm efficiency. [Program Outcome 10]

Laboratory Projects

Daily/Weekly programming assignments. No major projects.

2006 Laboratory Projects

In addition to daily homework exercises, the following projects were assigned:

• Program to count the number of inversions in a data set. (Variation of Merge sort) - 1.5 weeks
• Program to implement heaps and use them to mimic an on-line auction. – 2 weeks
• Sort detective – use empirical analysis to determine which buttons are using which sort algorithms. – 2 weeks
• Program to implement Binary search trees and use them to store and retrieve iTunes information – 2 weeks

Estimate CSAB Category Content

Data Structures (6 core / 2 advanced)
Algorithms (6 core / 2 advanced)
Software Design (1 core)
Computer Architecture
Programming Languages

Oral and Written Communication

None.

2006 Oral and Written Communication

Every student is required to submit at least 1 written reports (not including exams, tests, quizzes, or commented programs) of typically 5 pages and to make 0 oral presentations of typically 0 minutes duration.

Social and Ethical Issues

None.

Theoretical Content

• Time and space analysis of algorithms – 10 hours
• Solving recurrence relations – 4 hours
• Discussion of what factors contribute when choosing between algorithms – 2 hours
• Analysis of data structures – 4 hours
• NP-complete problems – 1 hour

Problem Analysis

• Students are expected to be able to look at code or pseudocode and analyze the time and space requirements.
• Students can also look at actual running times of algorithms and identify the type of algorithm that must have been used.
• Given a computational problem, students can analyze the problem requirements to decide which algorithm would best solve the problem.

Solution Design

All programming projects required a polymorphic solution. Code design was also graded in the projects.

Course Assessment

2008

Items to be assessed, assessement mechanism, and success criteria

The course material has been expanded to include NP/P material. The NP/P section quiz will be used to assess the student's understanding of P and NP problems. Success will be measured by an average score of 75 or higher on this quiz.

Assessment data and analysis

Two-days and the Final Exam period were set aside for the coverage and testing of material on P and NP. The average grade on the P/NP quiz was an 89.

Suggestions for next offering

I would recommend an additional emphasis on getting the students to read the book.

2007

Proposed changes from last offering

Will be changing the book to a more narrative book. The book includes less material but hopefully presents in an easier manner with motivation for why the particular algorithm is important.

I would recommend the use of this book in future iterations of this course. It was a quality book with good coverage of the topics without intimidating (other than the math) the students. (jkh - 16 May 2007)

2007 Items to be assessed, assessement mechanism, and success criteria

The ability of students to analyze a problem’s requirements and choose the best algorithm for solving the problem will be assessed based on programming assignments.

Assessment data and analysis

After covering the major three algorithmic techniques I designated as core (Divide-and-Conquer, Greedy, Dynmaic Programming) in detail, I presented the students with three assignments that tested their ability to determine the best algorithmic technique for solving.

MicroProgram 10 (Making Change) is a dynamic programming problem that initially looks like a problem ripe for the greedy approach. The students were able to see this after some time spent exploing a greedy solution. The average score for this assignment was an astounding 100.

Program 8 (Moldy Chocolate) is a divide-and-conquer problem. The students easily determined the nature of this problem and quickly starting working on a solution. The average score for this assignment was 94.5.

Program 9 (Tic-Tac-Toe II) is a greedy problem based on logical statements. The students easily determined the nature of this problem and worked toward a solution. A few students were tripped up by the logic and spent much longer an amount of time than was probably needed, but most were successful. The average grade was 97.5.

I was expecting the grades for these 3 assignments to be high (and they were) because this was not the first time we were exploring the topics. The high scores do show the students were able to implement solutions using the algorithmic techniques. This was certainly a success.

(jkh - 16 May 2007)

Proposed changes for 2008

I recommend the coverage of more material from the Dasgupta book (P, NP, NP-Completeness). (jkh - 16 May 2007)

Proposed changes for 2007

I recommend more programming projects and more emphasis on program design.

2006

2006 Proposed changes

This course remained the same as last year, with less in-class time spent on programming projects. More emphasis was placed on problem analysis.

2006 Items to be assessed, ...

The ability of students to analyze a problem’s requirements and choose the best algorithm for solving the problem will be assessed based on test questions.

Assessment data and analysis

Questions asking students to analyze a problem and choose the best algorithm were given on both tests and the final. The students have a better ability to analyze computational problems than in the past.

--Jkh 10:00, 16 May 2007 (EST)