### 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

## 20

## 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 20 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

8 November Day 22 Student Presentations Continuation of Turing Machines Example Peter Linz Chapter 9 addition p 242 movement refers to head moving program to add control unit transition functions Will add trick is to use unary notation as it makes programming easier input ID ID 1 1 1 0 1 1 ID ID output ID ID 1 1 1 1 1 0 ID ID Transition functions 5 are the program shorthand q0111011 means in state qo tape appears as 111011 and readwrite head Will read the symbol just to the right of the state qo next 5 010 1 010 1 R q011101191qo11011911q010119111q00119 5 010 0 011 1 R 1111q111 9 50111Q11R 11111q119111111q1D 9 5 011 D 012 D L 11111q21 9 5 012 1 013 0 L CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 1111q310 9 5 qs l qs l L 111q3110 911q31110 91q311110 9 q3111110 9 qu111110 9 5 013 D 014 D R q4111110 q4 is final therefore TM ends with correct answer 5 on the tape Notice how states are used to remember something NTO Chapter 31 review movement refers to tape moving data representation numbers people base 10 computers base 2 to make programming a TM easier we use unary counting sticks a non place value system Multiplication example Fig 312 input tape at top user s request 4 3 output results tape at bottom TM calculated 12 Program on page 209 transition state diagram delta function TM can solve any algorithm We believe that a TM is the simplest model of computation Dewdney s quintuple for a TM q s q s d q 2 current state s symbol under the tape q 2 state to transition to s symbol to write on tape d 2 direction to move tape Note TM programs are long because there is no real memory they can t count and remember a count in a variable instead states and temporary tape markers are used to remember stuff CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 Follow through multiplication and convince yourself how it works Multiplication is repeated addition write 3 groups of 4 on the tape WASSNIO create subtraction TM use the Visual Turing application in the lab Now insight into how to solve problem a see examples b work examples c deduce trial and error One possible general approach to subtract remove 1 s from both numbers evenly when smaller number runs out of Is the result is the answer WassnlO due Day 25 20 Nov CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 Day 25 28 November 2006 Wassn10 Due CS Reading Writing and Research 1 Reading How Silly question How do you Read much read widely read well Develop a professional library ll Writing Process Not just for reader writing is for the writer also to collect and organize thoughts I really learned something when I had to teach it Zobel Justin Writing for Computer Science The Art ofEffective Communication Singapore MA SpringerVerlag 1997 see httpgoannacsrmiteduaujZwritinghtml A scientific article is a description of new ideas and a demonstration of their correctness p xi Another important aspect of it writing is that the discipline of stating ideas as organized text forces authors to formulate and codify their thoughts Taking another perspective scientific papers are a way of communicating ideas of copying thoughts between minds Communication is at its most effective when the medium is as free as possible from distortion which in this case is bad writing of any kind Such distortion can be reduced by writing with clarity and simplicity and by making effective use of stylistic conventions p xii Writing Style General Guidelines Economy Text should be taut p 12 Tone Science writing should be objective and accurate p 13 Examples A small example often means the difference between communication and confusion p 16 CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 Motivation Not only should the parts of a paper be ordered in a logical way but this logic should be clearly communicated p 16 Eschew Obfuscation Ethics Grammar Beauty Elegance Remember the threepeat rule tell them what you are going to say say it tell them what you said Don t allow a major point to slip by unnoticed Ill Research Process Research is NOT looking something up on the internet yuck Brainstorm Research ismeans studying new areas perception re searching pouring over old areas reality looking at applications perhaps new areas connections structure to it qualitative quantitative repeatable presentation usable understandable scientific method definitions Research 2 to investigate thoroughly studious inquiry or examination especially investigation or experimentation aimed at the discovery and interpretation of facts revision of accepted theories or laws in the light of new facts or practical application of such new or revised theories or laws Scholarly or scientific investigation or inquiry historical research Specific methods in CS research A Quality Sources for Research 1 Currency 2 Primary Sources 3 Professional Journals 4 Authoritative Authors 5 Details and Data CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 B Ethics when conducting research 1 Informed Consent 2 Invasion of Privacy 3 Confidentiality 4 Protection from Danger 5 Knowledge of Outcome C Ethics when reporting research 1 Avoid Plagiarism using original work without proper citation or credit 2 Identify and reference all source material utilized Research Proposal Format Document Syntax and Semantics I Problem Statement and Goal This section contains a concise statement of the problem to be addressed ie why the research is being undertaken This section also contains a concise definition of the goal of the work ie what the research will accomplish Providing supporting evidence of the problem and goal from the literature II Relevance and Significance This section serves to strengthen the statement of the problem to be addressed This section contains a description of the value of the research ie why the research is important Demonstrate how the research will advance knowledge improve professional practice or contribute to understanding in the field III Barriers and Issues This sections addresses limitations and delimitations of the research This section addresses the underlying problems associated with the research process IV Approach Address how you eXpect to accomplish the stated goal V Resources A literature review is required to support your research This section contains an annotated bibliography of relevant works Computer Science Style Sheet Research Report Design and Organization CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 Title Page Research title author s name and affiliation Abstract concise description of the report Introduction problem and goal statements purpose and rationale Survey literature review and definitions Methodology procedure Results relevant research findings Summary conclusions References Annotated Bibliography Great Example of reading writing and research Computer Science as a Creative Activity Sayers Dorothy The Mind of the Maker San Francisco CA HarperCollins 1987 reprint of 1941 work The Creative Process is triune ldea Energy Power For every work or act of creation is threefold an earthly trinity to match the heavenly First not in time but merely in order of enumeration there is the Creative ldea passionless timeless beholding the whole work complete at once the end in the beginning and this is the image of the Father Second there is the Creative Energy or Activity begotten of the idea working in time from the beginning to the end with sweat and passion being incarnate in the bonds of matter and this is the image of the Word Third there is the Creative Power the meaning of the work and its response in the lively soul and this is the image of the indwelling Spirit And these three are one each equally in itself the whole work whereof none can eXist without other and this is the image of the Trinity Sayers citing her play The Zeal of Thy House p 3738 ldea l have a concept and image of a software product Energy 1 am performing the process of software engineering Power Someone is using my software to solve a problem CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 9 October Day 13 Chapter 2 Finite Automata FA A FA is a model of computation A FA is a mathematical model of HW A FA is an abstraction of HW Consider his black box analogy lnput gt Black Box gt Output lnside functions of black box are hidden Ex a TV we don t know how it works inside we give it input channel 30 and it gives us output Mathematical definition of FA Q is a set of states this is hidden in the black box Sigma is a set of input symbols delta is a function for moving from a state given an input this is the hidden portion of the black box Q includes an initial state and a final state An automaton accepts words in its language example for English problem is this string a word NOT 9 black box FA 9 yes accept OTN 9 black box FA 9 no Language we CS people care about is binary form Thus words are sequences of 1s 0s Job of a FA is to determine if input string is a word in the FA s language if yes then accept example use of an FA compiler checking syntax input strings of 1s and 0s is this input a syntactically valid word in the language C He is trying to uncover a pattern for the words that are accepted by the FA Pattern that was found was 0100101 001 is shorthand for any number of repetitions of the sequence 001 note that any number can also mean 0 thus valid words following the pattern 0100101 are CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 0101 0100101 0100100101 0100100100101 etc A state transition diagram is a convention used to represent FA How Input strings potential words are read one symbol letter at a time The FA moves between states given its current state and the input symbol 0 or 1 read If the input string is a real word in the language the FA will finish no more input in an accepting state Thus the goal of a FA is to finish in an accepting or final state It may not be possible to know exactly what is inside the black box since it is really hidden from view but we can know the sequences of 1s and 0s strings or words accepted by the black box ex we know that 0101 is accepted by 0110 is not The language accepted by a finite automaton by language we mean the good words or the accepted strings can be written as a Regular Expression RE RE is a formal way of writing an accepted language RE is shorthand don t have to list all of the accepted strings in a language ex how many strings are there answer infinite hard to list RE is a pattern for the accepted language 0 1 00 1 0 1 analogy its an algorithm for creating accepted strings it shows the form of good strings Rules for RE 0 and 1 are RE concatenation 01 is RE sum 01 better term is or is RE iteration is RE Ex 00100 note can just write it as 010 CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 can also just ignore other transitions and assume they go to trap or bad states Note if FA is in a final or accepting state When the input string is completely read then the string is in the language EX 0 11 note could write Without parentheses EX 011 EX 1101011 notes 11 concatenation must have this order or sequence sumor could have either left side sequence OR right side sequence iteration 0 or more n sequences It might help to list strings in the language 1 1 01 1 0 10 1 1 0 10 10 1 1 bad strings 101 0101001 Now draw diagram CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 6 November Day 21 Turing Machine is a fundamental CS concept Turing Alan Turing 19001955 British mathematician wanted to solve the universal computation problem TM is a mathematical model of computation collection of rules Importance of TM comes from the Turing Thesis which says TM is the simplest computer anything a computer can do can be done by a TM Follow handout chapter 9 of Peter Linz MCS 825 text p 230 draw tape tape consists of cells which may contain a symbol draw readwrite head lO control unit Processing note Linz moves readwrite head while Dewdney will move the tape TM model picture fig 91 Control unit is really a black box Outward appearance operation is simple 1 Move tape R or L 2 Read symbol off of tape 3 Write a new symbol on the tape tape is storage Power of a TM comes from what s inside the control unit a state machine Control unit Q set of internal states q0 2 initial state F 2 final states delta 2 transition function CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 Control unit of a TM is specified by key state transition functions delta Ex delta qO a 2 read as 1F current state is qO and read this symbol a off tape THEN 01L 01 R move to state q1 write new symbol d and move tape R TM s control unit is a collection of many state transition functions Follow through example 92 and 93 Visit TM simulator site at wwwcsbrownedupeoplengTuringtmachinehtml We have Visual Turing installed Chapter 31 in Dewdney Some insights into TMs A TM is essentially the same thing as its program control unit transition functions Figure 311 note his quintuple is really same as Linz transition function 01 S q S 01 current state current symbol new state new symbol direction to move tape highlevel explanation of Multiplication unary system large program figure 312 beginning and end for next time read and follow multiplication problem in Dewdney Presentations next time CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 3 October Day 11 Chapter 25 Fast Multiplication How do computers actually multiply numbers together We know the hardware performs the processing but how People memorize rules to help us with multiplication but what is the actual algorithm Consider standard multiplication in decimal eg 123 57 To calculate must a break up the problem by column b perform standard rules of multiplication eg 73 72 71 etc to form partial results and then c add the partial results together As the size of the multiplicands increases so too does the time to solve but not just linearly as we will see As multiplication problem input increases in size the time to solve increases too But is it linear no It is Cnz Why consider 123 vs 743116 57 4199 861 6688044 615 66880440 74311600 7011 2972464000 3120344084 Note that second problem is just twice as big n26 compared to first problem n23 yet the effort is much greater than twice ie not Cn linear remember n is the input size note that both dimensions of problem doubled twice as many columns and twice as many partial results binary arithmetic Consider addition regardless of the length or size number of bits n we will perform n 2 bit addition operations If we have two 10 bit words to add it will require 10 2 bit addition operations Thus time for add is On 1 O l O l O l l CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 Look at simple rules of binary addition 00 0 011 101 1110 Do these rules always hold true Yes Not thinking when you add just following rules algorithms Now we need to construct full adders to solve the general problem for any column 3 inputs two addends and a carryin 2 outputs sum and a carryout CSC325 constructed via gates show on 325 review day But multiplication is much slower Rules are easy 00 0 0120 10 0 1121 Eg multiply two 4bit values 1010 lOll l l O l l l 0 Why would we want to speed up multiplication examples eg graphics card etc response time throughput for CPU intensive jobs Is it possible to get multiplication to On What does gut say no if so multiplication could be performed as fast as addition Covered fast technique We want a tric to speed up multiplication want something faster Bottom of page 168 first speedup method we ll look at Separate each number in half sort of like scientific notation split each number into equal halves egxa2n2b yc2n2d CSC 490 Course Notes and Outline Dr Gary Locklair Fall 2006 a is upper half of first number thus it is shifted over by 2112 b is lower half of first number top ofpage 169 x is 1001 10 22 01 a 1 y is 1101 11 22 01 01 now Xybecomes a c 2n b c ZD2a d ZD2 b d distributive but if we first compute a c and b d don t have to compute b c a d as that equals ab cd ac bd thus bottom of page 169 Algorithm Techniques patterns Greedy for optimization saw in Minspan Divide and Conquer Note initially get it to 2n2 quot2 to go further continue to diVide and conquer ultimately could continue to diVide and conquer until limit of Onquot159 is reached 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

#### "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!"

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "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.