CS 22
Clab 5: Invariants, interesting functions,
Orders of growth, exponentiation, more with lists
<![CDATA[
Our student sysadmins will be hosting two Using
Unix II sessions this week (in the Sun Lab), at the following
times:
9-10pm this Wednesday night, January 30
8:30-9:30pm this Thursday night, January 31
These are intended for students new to Unix, and will
cover the following topics:
o Window Manager Basics (learn to use and customize your desktop)
o Command Repeating/Editing (save those precious keystrokes!)
o Job Control (go into an infinite loop will you? eat my Ctrl-C!)
o Organizing and Protecting Your Files (chmod, setfacl, etc)
o Man Pages (i.e.: how to glean what you want)
o Viewing Stuff (cat/less/more/grep)
o Input/Output Redirection ( '>', '<', '|', etc)
o More On Editors
o Review of Things Gone By
Let us know if you have questions: local-staff@cs.swarthmore.edu
]]>
Since you read about primality testing which is related to factoring,
if you have some good ideas, you could pick up an extra $200,000 by
factoring
<![CDATA[
RSA-2048
Prize: $200,000
Status: Not Factored
Decimal Digits: 617
25195908475657893494027183240048398571429282126204
03202777713783604366202070759555626401852588078440
69182906412495150821892985591491761845028084891200
72844992687392807287776735971418347270261896375014
97182469116507761337985909570009733045974880842840
17974291006424586918171951187461215151726546322822
16869987549182422433637259085141865462043576798423
38718477444792073993423658482382428119816381501067
48104516603773060562016196762561338441436038339044
14952634432190114657544454178424020924616515723350
77870774981712577246796292638635637328991215483143
81678998850404453640235273819513786365643912120103
97122822120720357
Decimal Digit Sum: 2738
]]>
See:
http://www.rsa.com/rsalabs/challenges/factoring/index.html
Here are some solutions to last clabs work. Make sure you understand
them thoroughly. If not, ask me about them.
<![CDATA[
;;; memb? returns #t if el is an element of list lst
;;; returns #f otherwise. Assume lst is a list.
(define (memb? el lst)
(cond
((null? lst) #f)
((equal? el (car lst)) #t)
(else (memb? el (cdr lst)))))
;; remove-first returns a list with the first occurrence of
;; sym removed from list l:
(define remove-first
(lambda (sym l)
(cond
((null? l) '())
((equal? (car l) sym) (cdr l))
(else (cons (car l) (remove-first sym (cdr l)))))))
]]>
Notice how we cons up a solution after cdring down one of the
parameters. This kind of structure is common to many list processing
solutions.
Review the material on pp.42-44.
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.3
Since I don't have superscripts
and subscripts on these pages, I will use log n to represent log to the
base 2 of n and x^y to represent x raised to the y power.
Recall that log n = k if 2^k = n. So log 16 = 4, log 32 = 5,
log 128 = 7, log 1024 = 10.
Keep in mind that:
100^3 = 1,000,000
log 1,000,000 is about 20
2^100 >> the number of microseconds since the big bang.
This means that if your algorithm has a running time of O(2^n) on
inputs of size n, and if want to use it on an input of size 100, you
will have to wait a long time to get an answer even if your computer
performs a million steps a second. O(n^3) algorithms don't take too
long on 100 inputs and O(log n) algorithms are fast on 1,000,000
inputs.
Now work through the 3 different exponential procedures given on pages
44-46. Use trace on them (you may want to trace * also) to help you
understand what they are doing. Make sure you understand how each of
them works and that (1) the first one requires O(n) time and space,
(2) the second one requires O(n) time and O(1) space, and (3) the
third one, fast-exp, requires O(log n) time and space. Ask questions
if you have them.
Now do exercise 1.16 on page 46. Make sure you test and debug (if necessary)
your procedure. You should
understand that this procedure takes O(log n) time and O(1) space.
Looking at traces should help you see this. But, don't hesitate
to ask questions if you have them.
I'll say a few words about invariants ex 1.16, 1.10,
and logs to base 2.
<![CDATA[
;;EXERCISE 1.10
(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1)
(A x (- y 1))))))
]]>
After I am finished (or while I am talking if you already understand all this
and can work quietly), define and debug the following functions.
Ask questions if you have them.
Make sure your language level is Full Scheme.
<![CDATA[
;; remove-all returns a list with all occurrences of sym
;; removed from list l:
(define remove-all
(lambda (sym l) .....
;; subst returns a list with all occurrences of old
;; replaced with new in list l:
(define subst
(lambda (new old l) ....
]]>