CS601 Algorithms, Architecture, and Languages (Proposed Course)

Course Description

Current research on, and cross-cutting interrelationships between computer algorithms, machine architecture, and languages. Covers asymptotic performance analysis including NP-completeness, modern parallel hardware including multicore, and grammars and parsing from regular expressions to BNF.

Tentative Schedule

1. Thu, Jan 15

   First day of instruction

   • Volunteer for lecture topics through spring break

2. Mon, Jan 19

   Alaska Civil Rights Day (no classes, most offices closed)

3. Tue, Jan 20

   Godel's incompleteness theorem & computability (NTO 5)

4. Wed, Jan 21

   Turing machines, and the halting problem (NTO 59)

5. Thu, Jan 22

   Noncomputable functions: busy beaver (NTO 39)

6. Mon, Jan 26

   Physical models for computation (NTO 33)

   • Homework: Turing Machines

7. Tue, Jan 27

   Turing machine simulation (NTO 31) & virtualization

8. Wed, Jan 28

   Chomsky hierarchy of languages (NTO 7)

9. Thu, Jan 29

   Pumping lemma (NTO 14) & non-regular languages

10. Fri, Jan 30

    Deadline for student- and faculty-initiated drops (course does not appear on academic record)

11. Mon, Feb 02

    Regular languages, and regular expression syntax

    • Homework: lexer design

12. Tue, Feb 03

    Lexer design in compilers

13. Wed, Feb 04

    String substitutions and halting (NTO 63)

14. Thu, Feb 05

    PROJECT: Preliminary proposals for semester projects

15. Mon, Feb 09

    Nondeterminism: NFA to DFA (NTO 26)

    • Homework: YACC

16. Tue, Feb 10

    Context Free Grammars, parsing, and compiler design

17. Wed, Feb 11

    Bottom-up and shift-reduce parsing, LALR

18. Thu, Feb 12

    YACC and BNF: LALR in practice

19. Sun, Feb 15

    Deadline to apply for spring 2015 graduation

20. Mon, Feb 16

    Introduction to graph data structures & algorithms

    • Homework: graph library

21. Tue, Feb 17

    Review: Prim's greedy minimum spanning tree (NTO 22)

22. Wed, Feb 18

    Traveling Salesman Problem, with application to 3D printer path planning

23. Thu, Feb 19

    Satisfiability and graph coloring (NTO 34)

24. Mon, Feb 23

    Boolean normal forms & circuits (NTO 13), with application to ASIC design

    • Homework: P vs NP

25. Tue, Feb 24

    NP Completeness and SAT (NTO 41)

26. Wed, Feb 25

    Proving NP-Completeness (NTO 54)

27. Thu, Feb 26

    Dynamic programming: filling in tables (NTO 601), with application to DNA sequencing

28. Mon, Mar 02

    Random and pseudorandom numbers (NTO 8)

    • Homework: Monte Carlo

29. Tue, Mar 03

    Monte Carlo integration, with application to financial modeling

30. Wed, Mar 04

    Probabilistic Algorithms: Rabin prime finding (NTO 50), with application to RSA encryption

31. Thu, Mar 05

    Approximate solutions to NP-hard problems

32. Mon, Mar 09

    Multi-precision arithmetic, with application to encryption on prime groups

    • Homework: RSA

33. Tue, Mar 10

    Number systems and base conversion, Chinese remainder theorem (NTO 42)

34. Wed, Mar 11

    Rivest-Shamir-Adleman (RSA) public key encryption

35. Thu, Mar 12

    PROJECT: Prior work reports

36. Fri, Mar 13

    Deadline for student- and faculty-initiated withdrawals (W grade appears on academic transcript)

37. Mon, Mar 16

    Spring break begins (no classes)

38. Fri, Mar 20

    Spring break--most offices closed

39. Mon, Mar 23

    Physical machines and silicon (NTO 56), with application to chip fabrication

    • Volunteer for lecture topics through final exam

40. Tue, Mar 24

    Triumph of the MOSFET, and quantum effects on modern silicon

41. Wed, Mar 25

    Shor factoring on quantum computers

42. Thu, Mar 26

    Adiabatic quantum machines and annealing

43. Mon, Mar 30

    Parallel computing machine topologies (NTO 62)

    • Homework: OpenMP + AVX

44. Tue, Mar 31

    Multicore, atomics, and locks

45. Wed, Apr 01

    SIMD: regular parallelism, with application to high-speed decryption

46. Thu, Apr 02

    Mixing SIMD and Multicore memory access

47. Mon, Apr 06

    GPU programming: fragment shaders

    • Homework: GPU

48. Tue, Apr 07

    GPU programming: CUDA

49. Wed, Apr 08

    Rendering the mandelbrot set per pixel (NTO 9)

50. Thu, Apr 09

    Cellular Automata: Conway's game of life (NTO 44)

51. Mon, Apr 13

    Floating point representation and roundoff

    • Homework: floating point

52. Tue, Apr 14

    Newton-Raphson root finding and convergence (NTO 21)

53. Wed, Apr 15

    Multi-precision floating point arithmetic, and Dekker addition

54. Thu, Apr 16

    Fast Multiplication: Karatsuba & Strassen (NTO 25)

55. Mon, Apr 20

    Genetic algorithms and crossover-friendly genomes (NTO 19)

    • Homework: neural networks

56. Tue, Apr 21

    Neural Network topology & training (NTO 36)

57. Wed, Apr 22

    Data compression via Huffman trees (NTO 52)

58. Thu, Apr 23

    Reed-Solomon error correcting codes

59. Fri, Apr 24

    SpringFest (no classes)

60. Mon, Apr 27

    Comprehensive exam after-action (part 1)

61. Tue, Apr 28

    Comprehensive exam after-action (part 2)

62. Wed, Apr 29

    PROJECT: Final presentations

63. Thu, Apr 30

    PROJECT: Final presentations cont'd

64. Mon, May 04

    Last day of instruction

65. Mon, May 04

    PROJECT: Final presentations cont'd

66. Tue, May 05

    Final exam, held in class

Grading Policies

Grades will be assigned based on the following percentage intervals:

A+

[99%, 100%)

A

[93%, 99%)

A-

[90%, 93%)

B+

[87%, 90%)

B

[83%, 87%)

B-

[80%, 83%)

C+

[77%, 80%)

C

[70%, 77%)

C-

[70%, 70%)

D+

[67%, 70%)

D

[63%, 67%)

D-

[60%, 63%)

F

[0%, 60%)

Course Format

Each day of class will begin with a half hour lecture, surveying and describing the course material.  The second half hour of each class will be a moderated discussion between the presenter, instructor, other students in the course, and invited guests.

To prepare an effective lecture, you must not only read the starter source material provided by the instructor, but also find, read, and evaluate other scholarly sources, for example via Google Scholar.  Lecture grades will be based on your written lecture outline submitted to the instructor before class; the quality of your slides, diagrams, videos, or other visual aids during the presentation; your ability to engage the audience; and your demonstrated depth and clarity of understanding of the subject and how it relates to the broader field.

• A grade "A" lecturer works to find and understand related papers, finds and focuses on the key areas, spends significant effort on interactive examples and demonstrations, practices their talk, and presents the material clearly and in context.
• A grade "B" lecturer finds a few related papers and some tangential ones, agglomerates them into a powerpoint with text and figures, and delivers a rambling and still incomplete talk.
• A grade "C" lecturer reads the book, prepares text-only powerpoint slides, reads them, and puts the audience to sleep.

To be prepared for the in-class discussion each day, you must at a minimum read the lecture notes, and the related book chapter and/or technical papers.  Discussion grades will be based on attendance, the quality of questions asked, and your demonstrated engagement with both the subject and discussion. The use of laptops or tablets during the lecture to take notes, run experiments, and seek out related scholarly information is highly encouraged, but their use to check email or write unrelated code is not. 

Our emphasis on clear written and oral communication skills is not to the exclusion of technical work, but due to the fact that employment, funding, and recognition all require both technical and communication skills!

Student Learning Outcomes

Students finishing this course will be able to:

• Explain how to determine if a problem is NP-Complete.
• Explain limits on computability, such as the busy beaver problem.
• Explain LALR parser generation, such as in a YACC parser.
• Design and construct parallel programs using at least one of multicore, SIMD, or GPU.
• Read and write technical literature, such as program documentation, white papers, and academic journal articles.

Policies

Students are expected to be at every class meeting on time, and are responsible for all class content, whether present or not. If absence from class is necessary, in-class work (other than quizzes) and homework may be made up only if the instructor is notified as soon as possible; in particular, absences due to scheduled events must be arranged ahead of time. Academic dishonesty will not be tolerated, and will be dealt with according to UAF procedures. Students in this class must pay the CS lab fee.

UAF academic policies http://www.uaf.edu/catalog/current/academics

CS Department policies http://www.cs.uaf.edu/departmental-policies/

Disabilities Services:

The UAF Office of Disability Services implements the Americans with Disabilities Act (ADA), and ensures that UAF students have equal access to the campus and course materials. I will work with the UAF Office of Disability Services (208 WHITAKER BLDG, 474-5655) to provide reasonable accommodation to students with disabilities.