### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Senior Seminar CSC 490

GPA 3.6

### View Full Document

## 27

## 0

## Popular in Course

## Popular in ComputerScienence

This 0 page Class Notes was uploaded by Mona D'Amore on Monday November 2, 2015. The Class Notes belongs to CSC 490 at Concordia University Wisconsin taught by Gary Locklair in Fall. Since its upload, it has received 27 views. For similar materials see /class/234351/csc-490-concordia-university-wisconsin in ComputerScienence at Concordia University Wisconsin.

## Reviews for Senior Seminar

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 11/02/15

11 October Day 14 CSC425 review 1 CPU A ALU B CU C Cache A ALU arithmeticlogic unit performs processing contains circuitry to add etc issues representation of numbers base 2 binary form 1 integers works well except for negative values as no way to have a sign in a bit a signed magnitude 3 2 b one s complement c two s complement 2 reals oats SES implementation no way to have a radix decimal point in a bit B CU control unit runs SW manager of system 1 instruction cycle a Fetch b Decode c Execute 2 Instruction sets CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 a CISC b RISC 3 Addressing a number i 3 address machine ADD Z Y X Z 6 Y X ii 2 address machine ADD Y X Y 6 Y X iii 1 address machine accumulator ADD X accumulator 6 accumulator X iiii 0 address machine stack ADD X pop add X push b modes i immediate operand is data value ii direct operand is memory address of value iii indirect operand is memory address of memory address of value C Cache highspeed memory onboard CPU not visible or usable by to programmer works via locality of reference CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 4 October Day 12 CSC 325 Computer Organization and Architecture 1 review see chapters 1 and 2 in CSAO for good reView material Architecture 2 highlevel View of HW a programmer s assembly lang machine lang View creates a computer family Organization 2 deep View of HW eX multiplication instruction existence of a multiplication instruction is architectural issue implementation of a multiplication instruction is an organizational issue Function what does it do Structure how is it connected Organization fundamental hw of processor unit component is switch transistor gate combination of transistors which performs a Boolean function Boolean functions not or and show truth tables gate symbols functionally complete set minimum number of diff functions needed to create any Boolean function a and or not b nand show nand show how to create not circuit using nand show how to create and circuit using nand CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 Day 28 7 December 2006 Pearl Harbor Day Handout example GRE Computer Science questions doublesided handout Exam review continued possible questions what does this code do read a listing should listing follow professional programming practice create C code to hash a record into an array create pseudo code to sort output of this circuit gates list gate symbols and names describe the function of this white box show gates ie create a truth table construct a halfadder or a mux or a demux from gates provide inputsoutputs via binary addition discuss phases in sw engr lifecycle compare and contrast OS memory manager and processor manager compare these two algorithms which is better BigO write a recursive function to compute n what data structure would you use for this program application what control structure would you use for this program application finite automata turing machine proof errordetection and correction capability CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 extra credit Don t forget about CSAO as great review Read chapter 11 in Brookshear student brainstorm list Draw process state diagram actually a joke as Paul Driver hates this DeVise a TM to add show deltas transition functions FA FSM Draw circuit for this Boolean function eg NOR using only AND OR Draw circuit for this truth table What does this circuit do Answer Via construction of truth table How do you solve problems Compare and contrast two PL paradigms SDLC Dorothy Sayers Mythical manmonth Knuth CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 5 September Day 3 Written Assignment0 due dates review note thread online Systems Assignment 0 due next time on Chemnitz Student Data CSC490 is the most important class you have Example Chapter 1 Read the entire chapter straight through ignoring things you don t understand immediately an application of abstraction Then reread the chapter for cognition comprehension Refer to other resources other texts eg Great Ideas effective 2 computable in a reasonable time Page 7 Problem 1 first part was straightforward second part was meant to illustrate a concept namely computers are dumb Problem 2 how would you approach it first understand the problem understand WALLPAPER algorithm general design pattern Outputs Inputs Processing ensure by actually creating and running code first understand output look at page 4 TEST remember create applications by specifying outputs first then inputs and finally algorithm deskcheck or walkthrough on algorithm ie playing computer algorithm on page 3 note add subnumbers 14 on inner loop statements corna cornb are the lower left corner of the image think of them as an offset for the picture from 00 image is created as a raster or bit map image envision coordinate system across CRT horizontal 0640 VGA vertical 0480 VGA side is students will determine in homework x and y are the location to plot or are they note we need meaningful variable names plot writes a dot no plot means no dot CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 what is int function truncate to integer value 675 becomes 6 if c is even then plot ie location ij is black if c is odd then don t plot ie location ij is white OK that s algorithm How does it work Read top of page 5 Now for an implementation See pages 67 Back to page 3 Good question how do we determine if c is even or odd 314 Look at implementation on page 7 What is modulo ie the mod function note he didn t define in text but used it in program on page 7 use other resource to look up if you don t know eg CSAO defines modulo on page 514 of 9th ed Modulo is remainder after division 73 is 2 remainder 1 thus 7 mod 3 is 1 note that a test for an even number is X mod 2 0 You should implement the original algorithm and test it ie run it before modifying the algorithm to solve the problem Creating the original algorithm will solidify many concepts and answer many necessary questions Create code using C simulate pixels bitmap with X and space use a 10X10 matriX create pattern from top to bottom a line at a time solve problem 2 also with X y and space decipher problem 2 hint residue classes of a number taken to mod 2 implementation issues operator precedence variable typing Note the Grand ldeas we ve discussed and used today CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 Questions on Systems Assignment 0 Due next time Day 4 Written Assignment 1 due in one week Day 5 Be sure to test Be sure to input data parameters from user CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 Day 27 5 December 2006 Exam review 9 Grand Ideas 1 Algorithm test Definition detailed and unambiguous set of step bystep procedures for solving a problem Brookshear quotes Concise definition of CS is problem solving Easy to see the connection between CS and algorithms Effective algorithm computable finite BigO measures the complexity of algorithms used to compare two algorithms timespace chp 15 detect control structures sequence selection repetition procedure call impact on big 0 Why There are multiple valid algorithms for the same problem eX searching sorting 2 Abstraction test Definition simplification by agreement note not fair to just simplify I made up my own language and it answers the test questions perfectly we use standard abbreviations to simplify that is there is an agreement connotes summary generalization CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 way to deal with complexity ex objectoriented information hiding using a builtin function eg cout don t have to know details only big picture 3 Automation test Definition runs autonomously by itself much power but also sometimes not noticed users may believe that they are running computer especially with interactive processing but this is not the case ex web server automatically services all requests for web pages concept of feedback outside inputs regulate function ex thermostat heater Illustrate these three in context of using a word processor 4 Information test Definition students define Information Processing is a slight misnomer computers don t process information as information is the ultimate goal goal of computer convert input data into output information Information Theory not Shannon theory source of information is intelligence information comes from intelligence intelligence is necessary to create information ex book recognize intelligent author via the information presented 5 Interface noun test Definition students define Because of layers of abstractions interfaces are built Ex User IF CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 Method of communications and control between user and computer User data and commands Computer information and messages 6 Intelligence test Definition students define very difficult to define ex Al create machine intelligence human level intelligence Turing Test what it is Illustrate these three in contect of using a web browser 7 Cognition definition understanding analysis process ex discover algorithm first step in problem solving 2 understand the problem how do we do it hard to answer typical answer heuristic which is This is the science in CS note an Al goal 8 Complexity definition difficult due to multiple interrelated components why are some things complex and others not eg a switch vs a microprocessor why is switch simple and CPU complex note CPU is a bunch of switches why quantity function how many structure interconnections eg space shuttle cockpit vs car dash dealing with complexity is a theme of CS realworld problems are complex air traffic control space shuttle avionics accounting etc oftentimes our solutions SW are complex today one method of dealing with complexity is 00 stuff this is old idea structured data abstraction info hiding etc 9 Creation definition building up making synthesis process CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 other steps in problem solving plan create code SW Engr focuses here Fred Brooks 2 CS is toolmaking IdeaEnergyPower Engineering of CS is here Illustrate these three in the context of the programming process CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 16 October Day 15 Chapter 3 Background on George Boole What is an Algebra Boolean Algebra variablesvalues 01 simpler than regular algebra each variable could have an infinite number of values operators functions 1 not 2 or 3 and 4 etc review truth table representation logic symbol and notational symbol A complete base is a subset of the 16 possible twovariable functions table on page 16 which can be used to perform any and all other Boolean functions In other words using just 3 say functions I can create the other 12 functions by using combinations of the three available in the complete base Ex And Or Not is a complete base Using combinations I can make any other Boolean function A Nand function can be made using a And and a Not for example Ex Nand is complete by itself Demo by creating And Or and Not using just Nand gates Electronics WorkBench demo ASSIGN7 Problem 1 How Either by showing that Nor can create all other 15 twovariable Boolean functions or by showing that Nor can create Or And and Not functions from just Nor gates CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 26 September Day 9 Collect Wassn3 Return review Sassnl presentation grades Return review Wasan if not done last time Chapter 15 time and space complexity quick overview BigO notation is used to analyze algorithms for efficiency example BigO notation O is order Example use we say an algorithm is On Order n Purpose of BigO notation convenience in comparing algorithms on time and space complexity usage What does this mean Ex which sorting algorithm is better bubble shell quick insertion etc Can answer based upon Order Quicksort which is On log n on average running on a small PC can beat bubble sort which is On2 running on a supercomputer if there are many values to sort To sort 1000000 numbers quicksort takes 20000000 steps on average while bubble sort takes 1000000000000 1 trillion steps Chapter problem find duplicates in a list Two possible algorithms 1 Scan 2 Stor Which is better SCAN algorithm a simpleminded doubly nested loop SCAN will exit stop when it finds the rst match Space complexity means memory or storage for data In this case it depends upon the size of array n Space complexity is On2 n for the number of array elements in A Where did the 2 come from need memory for variables i and j Time complexity means time of execution Count number of executed statements what s the worst case Answer O 3n2 a quadratic Time complexity starts out with an example say n is 4 outer loop i lt 1 3 inner loop j lt i1 to n 1st time outer loop i 1 tallest lines for outer loop inner loop j 2 i 1 CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 inner loop j 3 2nd time outer loop i 2 inner loop j 3 3rd time outer loop i 3 inner loop j 4 note example uses A 7 8 4 4 for time complexity assume each statement uses the same amount of time for execution just a benchmark Two questions on top of page 98 specific answers depend upon the actual values in the array A Problem is want to ensure that our list of integers is unique that is there are no duplicates in the list As soon as we find one duplicate then we can end SCAN algorithm one approach to solving that problem similar idea to the bubblesort it will keep scanning the list looking for duplicates First time it compares position 1 to all the others then compares position 2 to all the remaining etc Advantage of SCAN low space complexity Cn Disadvantage of SCAN higher time complexity CnAZ why is it CnAZ Don t consider the coefficient 3 and we only consider the greatest quantity eg nquot2 not n or 2 STOR algorithm a different approach to the problem employs a hashing function associative addressing test Associative addressing a value is the address Question SCAN vs STOR which should I use Which is better Does it matter which one I use Time complexity may help us decide which is better SCAN CnAZ STOR On CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 When n is large SCAN is much much slower than STOR But tradeoff is space complexity SCAN Cn we saw n2 locations needed STOR O STOR requires two arrays A contains the list itself B is the indexing array Ex A is of length 4 and contains 7 I 8 I 4 I 4 B is of length How big should it be How many locations the value of the largest integer in A determines the size number of locations in B so B is of length 8 and contains initially 0 I 0 I 0 I 0 I 0 I 0 I 0 I 0 0 and 1 are special markers a 1 means we ve seen this number in A The value 8 is largest value therefore B must be of size 8 BMW 9 BMW 9 BW note we should begin array with location 0 rather than 1 but Space complexity size of B is 2m where m is the size of values in A in bits B array is a flag array Index represents a possible number in the A array Contents are a flag 0 means we haven t seen this number in the A array before whereas 1 means the value has been seen Fig 151 is kind of silly The x axis isn t labeled but the crossover is 25 Who would run SCAN on array size of 1no duplicates or 2 Was sn4 CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 Explain in words Why SCAN is much slower than STOR Onquot2 gt On by examining the algorithms code both algorithms in C CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.