Example. Introduction to Programming (in C++) Loops. The while statement. Write the numbers 1 N. Assume the following specification:


 Emily Turner
 5 years ago
 Views:
Transcription
1 Example Introduction to Programming (in C++) Loops Assume the following specification: Input: read a number N > 0 Output: write the sequence N (one number per line) Jordi Cortadella, Ricard Gavaldà, Fernando Orejas Dept. of Computer Science, UPC This specification suggests some algorithm with a repetitive procedure. Syntax: The while statement while ( condition ) statement; (the condition must return a Boolean value) Semantics: Similar to the repetition of an if statement The condition is evaluated: If true, the statement is executed and the control returns to the while statement again. If false, the while statement terminates. Introduction to Programming Dept. CS, UPC 2 Write the numbers 1 N // Input: read a number N > 0 // Output: write the numbers 1...N (one per line) int N; cin >> N; int i = 1; while (i <= N) { // The numbers 1..i1 have been written cout << i << endl; i = i + 1; Introduction to Programming Dept. CS, UPC 3 Introduction to Programming Dept. CS, UPC 4
2 Product of two numbers A quick algorithm for the product //Input: read two nonnegative numbers x and y //Output: write the product x y // Constraint: do not use the operator // The algorithm calculates the sum x+x+x+ +x (y times) int x, y; cin >> x >> y; // Let x=a, y=b int p = 0; // Invariant: A B = p + x y while (y > 0) { p = p + x; y = y 1; cout << p << endl; Let p be the product x y Observation If y is even, p = (x 2) (y/2) If y is odd, p = x (y1) + x and (y1) becomes even Example: = 646 x y p Introduction to Programming Dept. CS, UPC 5 A quick algorithm for the product Introduction to Programming Dept. CS, UPC 6 Why is the quick product interesting? int x, y; cin >> x >> y; // Let x=a, y=b int p = 0; // Invariant: A B = p + x y while (y > 0) { if (y%2 == 0) { x = x 2; y = y/2; else { p = p + x; y = y 1; cout << p << endl; x y p Most computers have a multiply instruction in their machine language. The operations x 2 and y/2 can be implemented as 1bit left and right shifts, respectively. So, the multiplication can be implemented with shift and add operations. The quick product algorithm is the basis for hardware implementations of multipliers and mimics the paperandpencil method learned at school (but using base 2). Introduction to Programming Dept. CS, UPC 7 Introduction to Programming Dept. CS, UPC 8
3 Quick product in binary: example Counting a s 77 x 41 = x We want to read a text represented as a sequence of characters that ends with. We want to calculate the number of occurrences of the letter a We can assume that the text always has at least one character (the last. ) Example: the text Programming in C++ is amazingly easy!. has 4 a s Introduction to Programming Dept. CS, UPC 9 Counting a s // Input: sequence of characters that ends with. // Output: number of times a appears in the // sequence char c; cin >> c; int count = 0; // Inv: count is the number of a s in the visited // prefix of the sequence. c contains the next // nonvisited character while (c!=. ) { if (c == a ) count = count + 1; cin >> c; cout << count << endl; Introduction to Programming Dept. CS, UPC 10 Counting digits We want to read a nonnegative integer and count the number of digits (in radix 10) in its textual representation. Examples digits digits 8 1 digit 0 1 digit (note this special case) Introduction to Programming Dept. CS, UPC 11 Introduction to Programming Dept. CS, UPC 12
4 Counting digits Euclid s algorithm for gcd // Input: a nonnegative number N // Output: number of digits in N (0 has 1 digit) int N; cin >> N; int ndigits = 0; // Inv: ndigits contains the number of digits in the // tail of the number, N contains the remaining // part (head) of the number while (N > 9) { ndigits = ndigits + 1; N = N/10; // extracts one digit cout << ndigits + 1 << endl; Properties gcd(a,a)=a If a > b, then gcd(a,b) = gcd(ab,b) Example a b gcd (114, 42) Introduction to Programming Dept. CS, UPC 13 Euclid s algorithm for gcd // Input: read two positive numbers (a and b) // Output: write gcd(a,b) int a, b; cin >> a >> b; // Let a=a, b=b // gcd(a,b) = gcd(a,b) while (a!= b) { if (a > b) a = a b; else b = b a; cout << a << endl; Introduction to Programming Dept. CS, UPC 14 Faster Euclid s algorithm for gcd Properties gcd(a, 0)=a If b > 0 then gcd(a, b) = gcd(b, a mod b) Example a b Introduction to Programming Dept. CS, UPC 15 Introduction to Programming Dept. CS, UPC 16
5 Faster Euclid s algorithm for gcd // Input: read two positive numbers (a and b) // Output: write gcd(a,b) int a, b; cin >> a >> b; // Let a=a, b=b // gcd(a,b) = gcd(a,b) while (b!= 0) { int r = a%b; a = b; b = r; // Guarantees b < a (loop termination) cout << a << endl; Efficiency of Euclid s algorithm How many iterations will Euclid s algorithm need to calculate gcd(a,b) in the worst case (assume a > b)? Subtraction version: a iterations (consider gcd(1000,1)) Modulo version: 5 d(b) iterations, where d(b) is the number of digits of b represented in base 10 (proof by Gabriel Lamé, 1844) Introduction to Programming Dept. CS, UPC 17 Solving a problem several times In many cases, we might be interested in solving the same problem for several input data. Example: calculate the gcd of several pairs of natural numbers. Input Output Introduction to Programming Dept. CS, UPC 18 Solving a problem several times // Input: several pairs of natural numbers at the input // Output: the gcd of each pair of numbers written at the output int a, b; // Inv: the gcd of all previous pairs have been // calculated and written at the output while (cin >> a >> b) { // A new pair of numbers from the input while (b!= 0) { int r = a%b; a = Calculate b; gcd(a,b) and b = r; write the result into cout cout << a << endl; Introduction to Programming Dept. CS, UPC 19 Introduction to Programming Dept. CS, UPC 20
6 Solving a problem several times Prime number // Input: several pairs of natural numbers at the input // Output: the gcd of each pair of numbers written at the output int a, b; // Inv: the gcd of all previous pairs have been // calculated and written at the output while (cin >> a >> b) { // A new pair of numbers from the input while (b!= 0) { int r = a%b; a = b; b = r; cout << a << endl; A prime number is a natural number that has exactly two distinct divisors: 1 and itself. (Comment: 1 is not prime) Write a program that reads a natural number (N) and tells whether it is prime or not. Algorithm: try all potential divisors from 2 to N1 and check whether the remainder is zero. Introduction to Programming Dept. CS, UPC 21 Prime number // Input: read a natural number N>0 // Output: write is prime or is not prime depending on // the primality of the number int N; cin >> N; Introduction to Programming Dept. CS, UPC 22 Prime number Observation: as soon as a divisor is found, there is no need to check divisibility with the rest of the divisors. int divisor = 2; bool is_prime = (N!= 1); // 1 is not prime, 2 is prime, the rest enter the loop (assume prime) // is_prime is true while a divisor is not found // and becomes false as soon as the first divisor is found while (divisor < N) { if (N%divisor == 0) is_prime = false; divisor = divisor + 1; if (is_prime) cout << is prime << endl; else cout << is not prime << endl; However, the algorithm tries all potential divisors from 2 to N1. Improvement: stop the iteration when a divisor is found. Introduction to Programming Dept. CS, UPC 23 Introduction to Programming Dept. CS, UPC 24
7 Prime number Prime number: doing it faster // Input: read a natural number N>0 // Output: write is prime or is not prime depending on // the primality of the number int N; cin >> N; If N is not prime, we can find two numbers, a and b, such that: N = a b, with 1 < a b <N int divisor = 2; bool is_prime = (N!= 1); and with the following property: a N while (is_prime and divisor < N) { is_prime = N%divisor!= 0; divisor = divisor + 1; if (is_prime) cout << is prime << endl; else cout << is not prime << endl; There is no need to find divisors up to N1. We can stop much earlier. Note: a N is equivalent to a 2 N Introduction to Programming Dept. CS, UPC 25 Prime number: doing it faster // Input: read a natural number N>0 // Output: write is prime or is not prime depending on // the primality of the number Introduction to Programming Dept. CS, UPC 26 Iterations Is there any real difference? int N; cin >> N; int divisor = 2; bool is_prime = (N!= 1); while (is_prime and divisor divisor <= N) { is_prime = N%divisor!= 0; divisor = divisor + 1; if (is_prime) cout << is prime << endl; else cout << is not prime << endl; Number of bits Introduction to Programming Dept. CS, UPC 27 Introduction to Programming Dept. CS, UPC 28
8 In real time (N= ) The for statement > time prime_slow < number is prime u 0.004s 0: % > time prime_fast < number is prime 0.004u 0.000s 0: % Very often we encounter loops of the form: i = N; while (i <= M) { do_something; i = i + 1; This can be rewritten as: for (i = N; i <= M; i = i + 1) { do_something; Introduction to Programming Dept. CS, UPC 29 In general The for statement for ( S_init ; condition ; S_iter ) S_body ; is equivalent to: S_init; while ( condition ) { S_body ; S_iter ; Introduction to Programming Dept. CS, UPC 30 Writing the numbers in an interval // Input: read two integer numbers, N and M, // such that N <= M. // Output: write all the integer numbers in the // interval [N,M] int N, M; cin >> N >> M; for (int i = N; i <= M; ++i) cout << i << endl; Variable declared within the scope of the loop Autoincrement operator Introduction to Programming Dept. CS, UPC 31 Introduction to Programming Dept. CS, UPC 32
9 Calculate x y Drawing a triangle // Input: read two integer numbers, x and y, such that y >= 0 // Output: write x y int x, y; cin >> x >> y; int p = 1; for (int i = 0; i < y; ++i) p = p x; cout << p << endl; Given a number n (e.g. n = 6), we want to draw this triangle: * ** *** **** ***** ****** Introduction to Programming Dept. CS, UPC 33 Drawing a triangle // Input: read a number n > 0 // Output: write a triangle of size n Introduction to Programming Dept. CS, UPC 34 Perfect numbers A number n > 0 is perfect if it is equal to the sum of all its divisors except itself. int n; cin >> n; // Inv: the rows 1..i1 have been written for (int i = 1; i <= n; ++i) { // Inv: written j1 times in row i for (int j = 1; j <= i; ++j) cout << ; cout << endl; Examples 6 is a perfect number (1+2+3 = 6) 12 is not a perfect number ( ) Strategy Keep adding divisors until the sum exceeds the number or there are no more divisors. Introduction to Programming Dept. CS, UPC 35 Introduction to Programming Dept. CS, UPC 36
10 Perfect numbers Perfect numbers // Input: read a number n > 0 // Output: write a message indicating // whether it is perfect or not int n; cin >> n; Would the program work using the following loop condition? while (d <= n/2 and sum < n) int sum = 0, d = 1; // Inv: sum is the sum of all divisors until d1 while (d <= n/2 and sum <= n) { if (n%d == 0) sum += d; d = d + 1; if (sum == n) cout << is perfect << endl; else cout << is not perfect << endl; Can we design a more efficient version without checking all the divisors until n/2? Clue: consider the most efficient version of the program to check whether a number is prime. Introduction to Programming Dept. CS, UPC 37 Introduction to Programming Dept. CS, UPC 38
Introduction to Programming (in C++) Loops. Jordi Cortadella, Ricard Gavaldà, Fernando Orejas Dept. of Computer Science, UPC
Introduction to Programming (in C++) Loops Jordi Cortadella, Ricard Gavaldà, Fernando Orejas Dept. of Computer Science, UPC Example Assume the following specification: Input: read a number N > 0 Output:
More information8 Primes and Modular Arithmetic
8 Primes and Modular Arithmetic 8.1 Primes and Factors Over two millennia ago already, people all over the world were considering the properties of numbers. One of the simplest concepts is prime numbers.
More informationThe Euclidean Algorithm
The Euclidean Algorithm A METHOD FOR FINDING THE GREATEST COMMON DIVISOR FOR TWO LARGE NUMBERS To be successful using this method you have got to know how to divide. If this is something that you have
More informationElementary Number Theory and Methods of Proof. CSE 215, Foundations of Computer Science Stony Brook University http://www.cs.stonybrook.
Elementary Number Theory and Methods of Proof CSE 215, Foundations of Computer Science Stony Brook University http://www.cs.stonybrook.edu/~cse215 1 Number theory Properties: 2 Properties of integers (whole
More informationToday s Topics. Primes & Greatest Common Divisors
Today s Topics Primes & Greatest Common Divisors Prime representations Important theorems about primality Greatest Common Divisors Least Common Multiples Euclid s algorithm Once and for all, what are prime
More informationThe C++ Language. Loops. ! Recall that a loop is another of the four basic programming language structures
The C++ Language Loops Loops! Recall that a loop is another of the four basic programming language structures Repeat statements until some condition is false. Condition False True Statement1 2 1 Loops
More informationWhat is a Loop? Pretest Loops in C++ Types of Loop Testing. Countcontrolled loops. Loops can be...
What is a Loop? CSC Intermediate Programming Looping A loop is a repetition control structure It causes a single statement or a group of statements to be executed repeatedly It uses a condition to control
More informationCS 103X: Discrete Structures Homework Assignment 3 Solutions
CS 103X: Discrete Structures Homework Assignment 3 s Exercise 1 (20 points). On wellordering and induction: (a) Prove the induction principle from the wellordering principle. (b) Prove the wellordering
More information8 Divisibility and prime numbers
8 Divisibility and prime numbers 8.1 Divisibility In this short section we extend the concept of a multiple from the natural numbers to the integers. We also summarize several other terms that express
More informationName: Class: Date: 9. The compiler ignores all comments they are there strictly for the convenience of anyone reading the program.
Name: Class: Date: Exam #1  Prep True/False Indicate whether the statement is true or false. 1. Programming is the process of writing a computer program in a language that the computer can respond to
More informationBoolean Expressions, Conditions, Loops, and Enumerations. Precedence Rules (from highest to lowest priority)
Boolean Expressions, Conditions, Loops, and Enumerations Relational Operators == // true if two values are equivalent!= // true if two values are not equivalent < // true if left value is less than the
More informationHomework until Test #2
MATH31: Number Theory Homework until Test # Philipp BRAUN Section 3.1 page 43, 1. It has been conjectured that there are infinitely many primes of the form n. Exhibit five such primes. Solution. Five such
More informationCSI 333 Lecture 1 Number Systems
CSI 333 Lecture 1 Number Systems 1 1 / 23 Basics of Number Systems Ref: Appendix C of Deitel & Deitel. Weighted Positional Notation: 192 = 2 10 0 + 9 10 1 + 1 10 2 General: Digit sequence : d n 1 d n 2...
More informationQUIZII QUIZII. Chapter 5: Control Structures II (Repetition) Objectives. Objectives (cont d.) 20/11/2015. EEE 117 Computer Programming Fall2015 1
QUIZII Write a program that mimics a calculator. The program should take as input two integers and the operation to be performed. It should then output the numbers, the operator, and the result. (For
More informationFactoring Algorithms
Factoring Algorithms The p 1 Method and Quadratic Sieve November 17, 2008 () Factoring Algorithms November 17, 2008 1 / 12 Fermat s factoring method Fermat made the observation that if n has two factors
More informationLecture 3: Finding integer solutions to systems of linear equations
Lecture 3: Finding integer solutions to systems of linear equations Algorithmic Number Theory (Fall 2014) Rutgers University Swastik Kopparty Scribe: Abhishek Bhrushundi 1 Overview The goal of this lecture
More informationThe last three chapters introduced three major proof techniques: direct,
CHAPTER 7 Proving NonConditional Statements The last three chapters introduced three major proof techniques: direct, contrapositive and contradiction. These three techniques are used to prove statements
More informationIntroduction to Programming (in C++) Multidimensional vectors. Jordi Cortadella, Ricard Gavaldà, Fernando Orejas Dept. of Computer Science, UPC
Introduction to Programming (in C++) Multidimensional vectors Jordi Cortadella, Ricard Gavaldà, Fernando Orejas Dept. of Computer Science, UPC Matrices A matrix can be considered a twodimensional vector,
More informationEngineering Problem Solving with C++, Etter/Ingber
Engineering Problem Solving with C++, Etter/Ingber Chapter 3 Control Structures 1 Control structures Algorithm Development Conditional Expressions Selection Statements Repetition Statements Structuring
More informationChapter 3. if 2 a i then location: = i. Page 40
Chapter 3 1. Describe an algorithm that takes a list of n integers a 1,a 2,,a n and finds the number of integers each greater than five in the list. Ans: procedure greaterthanfive(a 1,,a n : integers)
More informationMath 319 Problem Set #3 Solution 21 February 2002
Math 319 Problem Set #3 Solution 21 February 2002 1. ( 2.1, problem 15) Find integers a 1, a 2, a 3, a 4, a 5 such that every integer x satisfies at least one of the congruences x a 1 (mod 2), x a 2 (mod
More information6. Control Structures
 35  Control Structures: 6. Control Structures A program is usually not limited to a linear sequence of instructions. During its process it may bifurcate, repeat code or take decisions. For that purpose,
More informationSection 4.2: The Division Algorithm and Greatest Common Divisors
Section 4.2: The Division Algorithm and Greatest Common Divisors The Division Algorithm The Division Algorithm is merely long division restated as an equation. For example, the division 29 r. 20 32 948
More informationThe Prime Numbers. Definition. A prime number is a positive integer with exactly two positive divisors.
The Prime Numbers Before starting our study of primes, we record the following important lemma. Recall that integers a, b are said to be relatively prime if gcd(a, b) = 1. Lemma (Euclid s Lemma). If gcd(a,
More informationInteger Factorization using the Quadratic Sieve
Integer Factorization using the Quadratic Sieve Chad Seibert* Division of Science and Mathematics University of Minnesota, Morris Morris, MN 56567 seib0060@morris.umn.edu March 16, 2011 Abstract We give
More information9 Control Statements. 9.1 Introduction. 9.2 Objectives. 9.3 Statements
9 Control Statements 9.1 Introduction The normal flow of execution in a high level language is sequential, i.e., each statement is executed in the order of its appearance in the program. However, depending
More informationInformatica e Sistemi in Tempo Reale
Informatica e Sistemi in Tempo Reale Introduction to C programming Giuseppe Lipari http://retis.sssup.it/~lipari Scuola Superiore Sant Anna Pisa October 25, 2010 G. Lipari (Scuola Superiore Sant Anna)
More informationIntermediate Math Circles March 7, 2012 Linear Diophantine Equations II
Intermediate Math Circles March 7, 2012 Linear Diophantine Equations II Last week: How to find one solution to a linear Diophantine equation This week: How to find all solutions to a linear Diophantine
More informationLecture 13  Basic Number Theory.
Lecture 13  Basic Number Theory. Boaz Barak March 22, 2010 Divisibility and primes Unless mentioned otherwise throughout this lecture all numbers are nonnegative integers. We say that A divides B, denoted
More informationFactoring & Primality
Factoring & Primality Lecturer: Dimitris Papadopoulos In this lecture we will discuss the problem of integer factorization and primality testing, two problems that have been the focus of a great amount
More informationGCDs and Relatively Prime Numbers! CSCI 2824, Fall 2014!
GCDs and Relatively Prime Numbers! CSCI 2824, Fall 2014!!! Challenge Problem 2 (Mastermind) due Fri. 9/26 Find a fourth guess whose scoring will allow you to determine the secret code (repetitions are
More informationChapter 8 Selection 81
Chapter 8 Selection 81 Selection (Decision) The second control logic structure is selection: Selection Choosing between two or more alternative actions. Selection statements alter the sequential flow
More informationIntroduction to Programming (in C++) Sorting. Jordi Cortadella, Ricard Gavaldà, Fernando Orejas Dept. of Computer Science, UPC
Introduction to Programming (in C++) Sorting Jordi Cortadella, Ricard Gavaldà, Fernando Orejas Dept. of Computer Science, UPC Sorting Let elem be a type with a operation, which is a total order A vector
More informationPublic Key Cryptography: RSA and Lots of Number Theory
Public Key Cryptography: RSA and Lots of Number Theory Public vs. PrivateKey Cryptography We have just discussed traditional symmetric cryptography: Uses a single key shared between sender and receiver
More informationBinary Number System. 16. Binary Numbers. Base 10 digits: 0 1 2 3 4 5 6 7 8 9. Base 2 digits: 0 1
Binary Number System 1 Base 10 digits: 0 1 2 3 4 5 6 7 8 9 Base 2 digits: 0 1 Recall that in base 10, the digits of a number are just coefficients of powers of the base (10): 417 = 4 * 10 2 + 1 * 10 1
More informationCHAPTER 5. Number Theory. 1. Integers and Division. Discussion
CHAPTER 5 Number Theory 1. Integers and Division 1.1. Divisibility. Definition 1.1.1. Given two integers a and b we say a divides b if there is an integer c such that b = ac. If a divides b, we write a
More informationPIC 10A. Lecture 7: Graphics II and intro to the if statement
PIC 10A Lecture 7: Graphics II and intro to the if statement Setting up a coordinate system By default the viewing window has a coordinate system already set up for you 1010 1010 The origin is in the
More informationRSA and Primality Testing
and Primality Testing Joan Boyar, IMADA, University of Southern Denmark Studieretningsprojekter 2010 1 / 81 Correctness of cryptography cryptography Introduction to number theory Correctness of with 2
More informationWhile Loop. 6. Iteration
While Loop 1 Loop  a control structure that causes a set of statements to be executed repeatedly, (reiterated). While statement  most versatile type of loop in C++ false while boolean expression true
More informationU.C. Berkeley CS276: Cryptography Handout 0.1 Luca Trevisan January, 2009. Notes on Algebra
U.C. Berkeley CS276: Cryptography Handout 0.1 Luca Trevisan January, 2009 Notes on Algebra These notes contain as little theory as possible, and most results are stated without proof. Any introductory
More informationArrays. number: Motivation. Prof. Stewart Weiss. Software Design Lecture Notes Arrays
Motivation Suppose that we want a program that can read in a list of numbers and sort that list, or nd the largest value in that list. To be concrete about it, suppose we have 15 numbers to read in from
More informationLecture 8: Binary Multiplication & Division
Lecture 8: Binary Multiplication & Division Today s topics: Addition/Subtraction Multiplication Division Reminder: get started early on assignment 3 1 2 s Complement Signed Numbers two = 0 ten 0001 two
More informationUnit 6. Loop statements
Unit 6 Loop statements Summary Repetition of statements The while statement Input loop Loop schemes The for statement The do statement Nested loops Flow control statements 6.1 Statements in Java Till now
More informationMATH 289 PROBLEM SET 4: NUMBER THEORY
MATH 289 PROBLEM SET 4: NUMBER THEORY 1. The greatest common divisor If d and n are integers, then we say that d divides n if and only if there exists an integer q such that n = qd. Notice that if d divides
More informationDIVISIBILITY AND GREATEST COMMON DIVISORS
DIVISIBILITY AND GREATEST COMMON DIVISORS KEITH CONRAD 1 Introduction We will begin with a review of divisibility among integers, mostly to set some notation and to indicate its properties Then we will
More informationDiscrete Mathematics, Chapter 4: Number Theory and Cryptography
Discrete Mathematics, Chapter 4: Number Theory and Cryptography Richard Mayr University of Edinburgh, UK Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapter 4 1 / 35 Outline 1 Divisibility
More informationNumber Theory. Proof. Suppose otherwise. Then there would be a finite number n of primes, which we may
Number Theory Divisibility and Primes Definition. If a and b are integers and there is some integer c such that a = b c, then we say that b divides a or is a factor or divisor of a and write b a. Definition
More informationAn Efficient RNS to Binary Converter Using the Moduli Set {2n + 1, 2n, 2n 1}
An Efficient RNS to Binary Converter Using the oduli Set {n + 1, n, n 1} Kazeem Alagbe Gbolagade 1,, ember, IEEE and Sorin Dan Cotofana 1, Senior ember IEEE, 1. Computer Engineering Laboratory, Delft University
More informationCommon Beginner C++ Programming Mistakes
Common Beginner C++ Programming Mistakes This documents some common C++ mistakes that beginning programmers make. These errors are two types: Syntax errors these are detected at compile time and you won't
More informationBasics of I/O Streams and File I/O
Basics of This is like a cheat sheet for file I/O in C++. It summarizes the steps you must take to do basic I/O to and from files, with only a tiny bit of explanation. It is not a replacement for reading
More informationThe While Loop. Objectives. Textbook. WHILE Loops
Objectives The While Loop 1E3 Topic 6 To recognise when a WHILE loop is needed. To be able to predict what a given WHILE loop will do. To be able to write a correct WHILE loop. To be able to use a WHILE
More informationGrade 7/8 Math Circles Fall 2012 Factors and Primes
1 University of Waterloo Faculty of Mathematics Centre for Education in Mathematics and Computing Grade 7/8 Math Circles Fall 2012 Factors and Primes Factors Definition: A factor of a number is a whole
More informationJ a v a Quiz (Unit 3, Test 0 Practice)
Computer Science S111a: Intensive Introduction to Computer Science Using Java Handout #11 Your Name Teaching Fellow J a v a Quiz (Unit 3, Test 0 Practice) Multiplechoice questions are worth 2 points
More informationTest1. Due Friday, March 13, 2015.
1 Abstract Algebra Professor M. Zuker Test1. Due Friday, March 13, 2015. 1. Euclidean algorithm and related. (a) Suppose that a and b are two positive integers and that gcd(a, b) = d. Find all solutions
More informationNumber Representation
Number Representation CS10001: Programming & Data Structures Pallab Dasgupta Professor, Dept. of Computer Sc. & Engg., Indian Institute of Technology Kharagpur Topics to be Discussed How are numeric data
More informationKeywords are identifiers having predefined meanings in C programming language. The list of keywords used in standard C are : unsigned void
1. Explain C tokens Tokens are basic building blocks of a C program. A token is the smallest element of a C program that is meaningful to the compiler. The C compiler recognizes the following kinds of
More informationBase Conversion written by Cathy Saxton
Base Conversion written by Cathy Saxton 1. Base 10 In base 10, the digits, from right to left, specify the 1 s, 10 s, 100 s, 1000 s, etc. These are powers of 10 (10 x ): 10 0 = 1, 10 1 = 10, 10 2 = 100,
More informationComputer and Network Security
MIT 6.857 Computer and Networ Security Class Notes 1 File: http://theory.lcs.mit.edu/ rivest/notes/notes.pdf Revision: December 2, 2002 Computer and Networ Security MIT 6.857 Class Notes by Ronald L. Rivest
More information13 Classes & Objects with Constructors/Destructors
13 Classes & Objects with Constructors/Destructors 13.1 Introduction In object oriented programming, the emphasis is on data rather than function. Class is a way that binds the data & function together.
More informationProblem Solving With C++
Dept. of Geomatics Eng. University of Tehran Cell: 0912 132 5823 Email: marajabi@ut.ac.ir http://www.marajabi.com Unfinished Business Casts (force an expression to be of a specific type) #include
More informationCompiler Construction
Compiler Construction Lecture 1  An Overview 2003 Robert M. Siegfried All rights reserved A few basic definitions Translate  v, a.to turn into one s own language or another. b. to transform or turn from
More informationFunctions Recursion. C++ functions. Declare/prototype. Define. Call. int myfunction (int ); int myfunction (int x){ int y = x*x; return y; }
Functions Recursion C++ functions Declare/prototype int myfunction (int ); Define int myfunction (int x){ int y = x*x; return y; Call int a; a = myfunction (7); function call flow types type of function
More informationCryptography and Network Security Number Theory
Cryptography and Network Security Number Theory XiangYang Li Introduction to Number Theory Divisors b a if a=mb for an integer m b a and c b then c a b g and b h then b (mg+nh) for any int. m,n Prime
More informationSection IV.1: Recursive Algorithms and Recursion Trees
Section IV.1: Recursive Algorithms and Recursion Trees Definition IV.1.1: A recursive algorithm is an algorithm that solves a problem by (1) reducing it to an instance of the same problem with smaller
More informationCOMPUTER SCIENCE 1999 (Delhi Board)
COMPUTER SCIENCE 1999 (Delhi Board) Time allowed: 3 hours Max. Marks: 70 Instructions: (i) All the questions are compulsory. (ii) Programming Language: C++ QUESTION l. (a) Why main function is special?
More informationDigitalCommons@University of Nebraska  Lincoln
University of Nebraska  Lincoln DigitalCommons@University of Nebraska  Lincoln MAT Exam Expository Papers Math in the Middle Institute Partnership 71007 Pythagorean Triples Diane Swartzlander University
More informationHandout NUMBER THEORY
Handout of NUMBER THEORY by Kus Prihantoso Krisnawan MATHEMATICS DEPARTMENT FACULTY OF MATHEMATICS AND NATURAL SCIENCES YOGYAKARTA STATE UNIVERSITY 2012 Contents Contents i 1 Some Preliminary Considerations
More informationLecture 3. Arrays. Name of array. c[0] c[1] c[2] c[3] c[4] c[5] c[6] c[7] c[8] c[9] c[10] c[11] Position number of the element within array c
Lecture 3 Data structures arrays structs C strings: array of chars Arrays as parameters to functions Multiple subscripted arrays Structs as parameters to functions Default arguments Inline functions Redirection
More informationContinued Fractions and the Euclidean Algorithm
Continued Fractions and the Euclidean Algorithm Lecture notes prepared for MATH 326, Spring 997 Department of Mathematics and Statistics University at Albany William F Hammond Table of Contents Introduction
More informationBreaking The Code. Ryan Lowe. Ryan Lowe is currently a Ball State senior with a double major in Computer Science and Mathematics and
Breaking The Code Ryan Lowe Ryan Lowe is currently a Ball State senior with a double major in Computer Science and Mathematics and a minor in Applied Physics. As a sophomore, he took an independent study
More informationTo convert an arbitrary power of 2 into its English equivalent, remember the rules of exponential arithmetic:
Binary Numbers In computer science we deal almost exclusively with binary numbers. it will be very helpful to memorize some binary constants and their decimal and English equivalents. By English equivalents
More informationStatements and Control Flow
Contents 1. Introduction 2. Types and Variables 3. Statements and Control Flow 4. Reading Input 5. Classes and Objects 6. Arrays 7. Methods 8. Scope and Lifetime 9. Utility classes 10. Introduction to
More informationJust the Factors, Ma am
1 Introduction Just the Factors, Ma am The purpose of this note is to find and study a method for determining and counting all the positive integer divisors of a positive integer Let N be a given positive
More informationLecture 2 Notes: Flow of Control
6.096 Introduction to C++ January, 2011 Massachusetts Institute of Technology John Marrero Lecture 2 Notes: Flow of Control 1 Motivation Normally, a program executes statements from first to last. The
More informationPractice Questions. CS161 Computer Security, Fall 2008
Practice Questions CS161 Computer Security, Fall 2008 Name Email address Score % / 100 % Please do not forget to fill up your name, email in the box in the midterm exam you can skip this here. These practice
More informationPrimes in Sequences. Lee 1. By: Jae Young Lee. Project for MA 341 (Number Theory) Boston University Summer Term I 2009 Instructor: Kalin Kostadinov
Lee 1 Primes in Sequences By: Jae Young Lee Project for MA 341 (Number Theory) Boston University Summer Term I 2009 Instructor: Kalin Kostadinov Lee 2 Jae Young Lee MA341 Number Theory PRIMES IN SEQUENCES
More informationNumeral Systems. The number twentyfive can be represented in many ways: Decimal system (base 10): 25 Roman numerals:
Numeral Systems Which number is larger? 25 8 We need to distinguish between numbers and the symbols that represent them, called numerals. The number 25 is larger than 8, but the numeral 8 above is larger
More informationCS 241 Data Organization Coding Standards
CS 241 Data Organization Coding Standards Brooke Chenoweth University of New Mexico Spring 2016 CS241 Coding Standards All projects and labs must follow the great and hallowed CS241 coding standards.
More informationLecture Notes on Linear Search
Lecture Notes on Linear Search 15122: Principles of Imperative Computation Frank Pfenning Lecture 5 January 29, 2013 1 Introduction One of the fundamental and recurring problems in computer science is
More informationMATH10040 Chapter 2: Prime and relatively prime numbers
MATH10040 Chapter 2: Prime and relatively prime numbers Recall the basic definition: 1. Prime numbers Definition 1.1. Recall that a positive integer is said to be prime if it has precisely two positive
More informationElementary Number Theory
Elementary Number Theory A revision by Jim Hefferon, St Michael s College, 2003Dec of notes by W. Edwin Clark, University of South Florida, 2002Dec L A TEX source compiled on January 5, 2004 by Jim Hefferon,
More informationGrade 6 Math Circles. Binary and Beyond
Faculty of Mathematics Waterloo, Ontario N2L 3G1 The Decimal System Grade 6 Math Circles October 15/16, 2013 Binary and Beyond The cool reality is that we learn to count in only one of many possible number
More informationA Study on the Necessary Conditions for Odd Perfect Numbers
A Study on the Necessary Conditions for Odd Perfect Numbers Ben Stevens U63750064 Abstract A collection of all of the known necessary conditions for an odd perfect number to exist, along with brief descriptions
More informationTHE NUMBER OF REPRESENTATIONS OF n OF THE FORM n = x 2 2 y, x > 0, y 0
THE NUMBER OF REPRESENTATIONS OF n OF THE FORM n = x 2 2 y, x > 0, y 0 RICHARD J. MATHAR Abstract. We count solutions to the RamanujanNagell equation 2 y +n = x 2 for fixed positive n. The computational
More informationSettling a Question about Pythagorean Triples
Settling a Question about Pythagorean Triples TOM VERHOEFF Department of Mathematics and Computing Science Eindhoven University of Technology P.O. Box 513, 5600 MB Eindhoven, The Netherlands EMail address:
More informationSUBGROUPS OF CYCLIC GROUPS. 1. Introduction In a group G, we denote the (cyclic) group of powers of some g G by
SUBGROUPS OF CYCLIC GROUPS KEITH CONRAD 1. Introduction In a group G, we denote the (cyclic) group of powers of some g G by g = {g k : k Z}. If G = g, then G itself is cyclic, with g as a generator. Examples
More informationTranslating to Java. Translation. Input. Many Level Translations. read, get, input, ask, request. Requirements Design Algorithm Java Machine Language
Translation Translating to Java Introduction to Computer Programming The job of a programmer is to translate a problem description into a computer language. You need to be able to convert a problem description
More information15 Prime and Composite Numbers
15 Prime and Composite Numbers Divides, Divisors, Factors, Multiples In section 13, we considered the division algorithm: If a and b are whole numbers with b 0 then there exist unique numbers q and r such
More informationCOMPSCI 210. Binary Fractions. Agenda & Reading
COMPSCI 21 Binary Fractions Agenda & Reading Topics: Fractions Binary Octal Hexadecimal Binary > Octal, Hex Octal > Binary, Hex Decimal > Octal, Hex Hex > Binary, Octal Animation: BinFrac.htm Example
More informationALGORITHMS AND FLOWCHARTS
ALGORITHMS AND FLOWCHARTS A typical programming task can be divided into two phases: Problem solving phase produce an ordered sequence of steps that describe solution of problem this sequence of steps
More informationF ahrenheit = 9 Celsius + 32
Problem 1 Write a complete C++ program that does the following. 1. It asks the user to enter a temperature in degrees celsius. 2. If the temperature is greater than 40, the program should once ask the
More informationBinary Division. Decimal Division. Hardware for Binary Division. Simple 16bit Divider Circuit
Decimal Division Remember 4th grade long division? 43 // quotient 12 521 // divisor dividend 480 4136 5 // remainder Shift divisor left (multiply by 10) until MSB lines up with dividend s Repeat until
More informationPositional Numbering System
APPENDIX B Positional Numbering System A positional numbering system uses a set of symbols. The value that each symbol represents, however, depends on its face value and its place value, the value associated
More informationMS Visual C++ Introduction. Quick Introduction. A1 Visual C++
MS Visual C++ Introduction 1 Quick Introduction The following pages provide a quick tutorial on using Microsoft Visual C++ 6.0 to produce a small project. There should be no major differences if you are
More informationa 11 x 1 + a 12 x 2 + + a 1n x n = b 1 a 21 x 1 + a 22 x 2 + + a 2n x n = b 2.
Chapter 1 LINEAR EQUATIONS 1.1 Introduction to linear equations A linear equation in n unknowns x 1, x,, x n is an equation of the form a 1 x 1 + a x + + a n x n = b, where a 1, a,..., a n, b are given
More informationSome facts about polynomials modulo m (Full proof of the Fingerprinting Theorem)
Some facts about polynomials modulo m (Full proof of the Fingerprinting Theorem) In order to understand the details of the Fingerprinting Theorem on fingerprints of different texts from Chapter 19 of the
More informationSources: On the Web: Slides will be available on:
C programming Introduction The basics of algorithms Structure of a C code, compilation step Constant, variable type, variable scope Expression and operators: assignment, arithmetic operators, comparison,
More informationPassing 1D arrays to functions.
Passing 1D arrays to functions. In C++ arrays can only be reference parameters. It is not possible to pass an array by value. Therefore, the ampersand (&) is omitted. What is actually passed to the function,
More informationRegression Verification: Status Report
Regression Verification: Status Report Presentation by Dennis Felsing within the Projektgruppe Formale Methoden der Softwareentwicklung 20131211 1/22 Introduction How to prevent regressions in software
More informationNumber Theory: A Mathemythical Approach. Student Resources. Printed Version
Number Theory: A Mathemythical Approach Student Resources Printed Version ii Contents 1 Appendix 1 2 Hints to Problems 3 Chapter 1 Hints......................................... 3 Chapter 2 Hints.........................................
More information