Computer Science 362.01
Data Structures and Algorithms

Spring 2013

Professor Valente

 

MEETINGS:

            MWF 1:30-2:20 in Bagby 020

 

OFFICE HOURS:

            MWR 2:30PM-4:00PM

 

TEXTBOOK:

            Introduction to the Design an Analysis of Algorithms, 3rd Edition

 

DESCRIPTION:

 

This course concerns itself with the study of algorithms, including how best to design them, how to analyze them for efficiency and determine whether they are correct.   Naturally, many of the historically important algorithms have been and continue to be strictly numerical in nature (for example, computing the GCD of two numbers, and performing modular exponentiation).  Of course, the other algorithms we study are important because the ADTs we design rely heavily on efficient algorithms for their processing.  Thus, in this course, we will look at algorithms and problem-solving strategies we have studied before, but with an eye towards careful analysis.  With this analysis, we’ll be able to determine whether or not an algorithm is efficient or even “feasible”, and accurately predict running times for programs that use these algorithms.  The analysis itself will require a Mathematics “toolbox” so-to-speak, some basic tools from which we will study early, but some others that we’ll introduce as needed for particular problems.  Finally, this is the course in which a most important topic is studied in detail: Graph Theory.  Besides satisfying us CS purists by providing a rich data structure with interesting mathematical properties to study, graphs also provide us with an important way to model many problems, particularly problems related to networks.  Graphs also provide very good examples of and provide insights into the study of NP-Complete problems.

 

 GRADING:

 

            In-class exams (March 1st and April 19th) count 30%.

            Homework (which may include programming) counts 30%.

            Final Exam (scheduled for Tuesday May 7th at 2PM) counts 25%.

            Class Attendance and Participation counts 15%.

                Based on 20 points for class attendance – each unexcused absence costs you 3 points.

                Also based on 30 points for daily problem solving tasks.

                    For this latter component, you will be given 0 to 2 points for solving a problem

                    correctly [0 = no show / couldn’t get started on it,   1 = good effort but not correct, 2 = correct]

 

 

TENTATIVE SCHEDULE:

 

 

Week Of         Topic                                                                          Read

 

Jan 16th            Course Intro, Analysis Framework                             Chapter 1 and Section 2.1.

 

                       

Jan 21st            The Fundamentals of Algorithm Analysis:

                        Growth Rates, Analysis of Iterative Algorithms        Sections 2.2 and 2.3

Jan 28th            Analysis of Recursive Algorithms,

                        Solving Recurrences                                                   Sections 2.4 and 2.5

 

Feb 4th, Feb 11th         

                        Brute Force Algorithms                                              Chapter 3

                        Sorting, Searching, String Matching

                        Exhaustive Search and DFS, BFS

 

Feb 18th, Feb 25th

                        Decrease and Conquer Algorithms                             Chapter 4

                        Binary Search Tree Algorithms

 

                                    TEST 1 IS ON FRIDAY, MARCH 1st

 

Mar 4th             Divide and Conquer Algorithms                                Sections 5.1, 5.2

                        Mergesort and Quicksort

 

Mar 18th           Binary Tree Traversals                                                Section 5.3

                        Fast Multiplication Algorithms                                   Section 5.4

 

Mar 25th           Transform and Conquer Algorithms                           Section 6.1

Heaps  and Heap Sort                                                 Section 6.4

Apr 1st             Horner’s Rule and Binary Exponentiation                 Section 6.5

                        Other topics from Chapter 6 (time permitting)           Section 6.6

 

Apr 8th             Sorting By Counting, String Matching                       Sections 7.1, 7.2

Apr 15th           Hashing                                                                       Section 7.3

 

                                    TEST 2 IS ON FRIDAY, APRIL 19th 

 

Apr 22nd             Dynamic Programming                                               Chapter 8

Apr 29th