Analysis of Algorithms

This is the World Wide Web page for CS 3343, section 1, Spring 1998. It contains several links to important information about the course. The contents of this page will change over the course of the semester; be sure to reload this page often. If you are unfamiliar with using the Web, select the underlined or highlighted word "introduction" in the paragraph below (click the left mouse button while the pointer is over the word in Netscape, or use the arrow keys to highlight the word and press RETURN in lynx). This will start you off on how to use the Web and other computer systems at UTSA.

Read my introduction to using computers at UTSA for information about how to use the web browsers, read and post news, compile programs, and get Linux software so you can do all that stuff and more at home.

Here is the syllabus for the course. It contains a description of the course, including percentages for tests, assignments and so forth.

The midterm exam is scheduled for Thursday, March 5, 1998 with an in-class
review the preceding Tuesday. Here is a review
with sample questions **and solutions** you might find helpful in preparing for the
exam.
The exam will cover topics from the beginning of the semester
until the February 26 class lecture.

The final exam is scheduled for Monday, May 4, 1998 at 10:30am. There will be an in-class review Tuesday, April 28 1998. Here is a set of review questions of the type likely to occur on the final. The final will concentrate on material from lectures 15 through 25, but anything before then is also fair game. You are also responsible for material from assignment 5 turned in by other people. You should be able to answer simple True/False questions about the algorithms your classmates presented on the newsgroup.

Here are our assignments:

- Assignment 1, due Tuesday, January 27, 1998.
- Solutions to Assignment 1
- Assignment 2, due Thursday, February 5, 1998.
- Assignment 3, due Tuesday, February 17, 1998.
- Assignment 4, due Tuesday, March 3, 1998.
- Assignment 5, due Tuesday, April 7 and April 14, 1998.
- Assignment 6, due Tuesday, April 28, 1998.

This news article gives the class results for assignment 6.

Notes from selected class lectures:

- Lecture 1: Introduction: Analysis of Selection Sort
- Lecture 2: Introduction: Analysis of Merge Sort
- Lecture 3: Asymptotic Notation
- Lecture 4: Asymptotic Notation Continued
- Lecture 5: Heapsort
- Lecture 6: Heapsort Continued
- Lecture 7: Priority Queues (more heaps)
- Lecture 8: Quicksort
- Lecture 9: Bounds on Sorting and Linear Time Sorts
- Lecture 10: Stable Sorts and Radix Sort
- Lecture 11: Begin Dynamic Programming
- Lecture 12: More Dynamic Programming
- Lecture 13: Begin Greedy Algorithms: Huffman's Algorithm
- Lecture 14: Dÿkstra's Algorithm
- Lecture 15: Beyond Asymptotic Analysis: Memory Access Time
- Lecture 16: B-Trees
- Lecture 17: More B-Trees: Insertion and Splitting
- Lecture 18: Union/Find
- Lecture 19: Warshall's Algorithm, Floyd's Algorithm
- Lecture 20: Large Integer Arithmetic
- Lecture 21: RSA Public-Key Cryptosystem
- Lecture 22: Begin Algorithms and Structural Complexity Theory
- Lecture 23: Continue Algorithms and Structural Complexity Theory
- Lecture 24: End Algorithms and Structural Complexity Theory
- Lecture 25: Generating Permutations and Combinations

Our class newsgroup is utsa.cs.3343.d .
Go there for discussion of our class, and contribute if you like. You can
also use the Unix program `trn` to read the newsgroup.
(You can only read this newsgroup from a UTSA machine.)

Here is UTSA's official Web page . Remember, Friday, March 13, 1998 is the last day to drop a class and receive an automatic grade of W.

See the Division of Computer Science Web page for information about CS at UTSA.

This page was put together by the instructor,
Daniel Jimenez
(`djimenez@ringer.cs.utsa.edu`).