Computational Geometry: mudanças entre as edições

De Pontão Nós Digitais
Ir para navegaçãoIr para pesquisar
(log juliana)
 
(31 revisões intermediárias pelo mesmo usuário não estão sendo mostradas)
Linha 1: Linha 1:
= ////////// Under Construction ////////// =
= ////////// Under Construction ////////// =


This is the main page of a graduate level course (Msc and PhD) in computational geometry being taught in 2019/2 at the Polytechnic Institute [http://pt.wikipedia.org/wiki/IPRJ IPRJ]/UERJ. It is generally useful for programmers at the advanced level in the fields of machine learning, scientific simulations, graphics, computer vision and and multimedia programming.
[[Arquivo:Computational-geometry-concept-diagram.png|500px|center]]
 
This is the main page of a graduate level course in computational geometry being taught in 2019/2 at the Polytechnic Institute [http://pt.wikipedia.org/wiki/IPRJ IPRJ]/UERJ. It is generally useful for programmers at the advanced level in the fields of machine learning, scientific simulations, graphics, computer vision and and multimedia programming.
 
 
 
 
== General Info ==
* Instructor: prof. [http://rfabbri.github.io Ricardo Fabbri], Ph.D. Brown University
* Meeting times: Wednesdays 7:50-11:30, Thursdays 7:50-9:40, and 15:00-17:00, room 110.
* Evaluation criteria: at least 2 quizzes (40%), practical projects (60%).
* Forum for file exchange and discussion: email and IRC #labmacambira


== Lecture Log ==
== Lecture Log ==


 
=== Part 1: C++ Programming Practice and Review ===
=== Wed 9Out19 (twice lecture load) ===
==== Wed 9Out19 (twice lecture load) ====
* Hello world
* Hello world
** for loop print 10x
** for loop print 10x
Linha 13: Linha 24:
* Farenheit to/from celcius program: homework
* Farenheit to/from celcius program: homework


=== Wed 16Oct19 ===
==== Wed 16Oct19 ====
* Show results of Farenheit to Celsius
* Show results of Farenheit to Celsius
* Learn Codeblocks
* Learn Codeblocks


=== Thu 17Oct19 ===
==== Thu 17Oct19 ====
* Print function graph (K&R Histogram)
* Print function graph (K&R Histogram)
** Horizontal
** Horizontal
Linha 23: Linha 34:
*** Learn first simple sort algorithm using max
*** Learn first simple sort algorithm using max


== Wed 23Out19 ==
==== Wed 23Out19 (twice lecture load) ====
** Vertical Function graph (K&H Histogram)
* Due: simple sort using max
* bucket sort (class exercise). Due. (student juliana: done)
* Other simple sorts. Insertion, selection,  bubble
** Basic building block: insert on sorted array, keeping it sorted
* Theory: arrays.


== Tarefas ==
==== Thu 24Out19  ====
* Overdue: simple sort using max
** Did: used max function
*** at first, max function without index
**** Sub-exercise: implement max of an array to return index, recursive and non-recursive
*** did: sort with max function, with index
** Question: does it work with repeated entries?
** If you have a vector of float height[num_people] and age[num_people], and there is a repeated age, can you print ages and respective heights sorted by age, without losing information?
** What is a stable sort
*Vector and cross product exercise
** Exercise from qualify
* Sort building blocks


=== Hello World ===
==== Wed 30Out19 ====
* Overdue: Vertical Function graph (K&H Histogram)
* Due: Insert on sorted array (Juliana: 9,5)
* Due: Merge two sorted arrays as warmup for next lecture (Juliana: 5)
* Due: Simple sort by recursive and non-recursive max is stable? argue in PDF (Juliana 0)
* Content
** Reviewed due homework
** Pointers, references
** Arrays and pointers
** Matrices as multidimensional arrays. Pointers.
** Malloc for arrays and matrices
** Structs
** Void *
** Pointers to functions
==== Thu 31Out19 ====
* Due: better sorted insert
* Due: max() in vertical histogram
* Due: more efficient merge
* Bitwise operators. Modulo operator.
* Excercises: one regarding Matrices, another regarding number and bit manipulation.
* Image lookup table for sorting intensities


=== Celsius to/from Farenheit ===
==== Wed 13Out19 ====
* Exam: programming fundamentals


=== Print Function graph (K&R Histogram) ===
==== Future ====
* Intro to advanced sorts: Merge sort, Quick Sort
** Basic building blocks:
*** merge: merge two sorted arrays into a sorted array.
*** partition an arbitrary array into smaller and larger than a given t


=== Sort using max function ===
== Tasks + Homework ==


=== Bucket sort ===
=== Part 1: C++ Programming practice and Review ===
 
==== Hello World ====
 
==== Celsius to/from Farenheit ====
 
==== Print Function graph (K&R Histogram): horizontally ====
* Sub exercise: max function
 
==== Implement max function recursively ====
 
==== Sort using max function ====
 
==== Print Function graph (K&R Histogram): vertically ====
 
==== Bucket sort ====
 
=== Vector and cross product exercise ===
* Exercise from qualify
 
Dados 2 vetores de inteiros A=[a1,a2,a3] e B=[b1,b2,b3] :
# Crie uma função que leia estes vetores do teclado
# Crie um função que calcule o produto escalar entre estes vetores.
# Crie uma função que calcule o produto vetorial entre estes vetores.
# Crie uma função que imprima o resultado na tela
:produto escalar <code>C = A*B=a1b1 + a2b2 + a3b3</code>
:produtor vetorial <code>C =[a2b3 – a3b2, a3b1 – a1b3, a1b2 - a2b1]</code>
 
 
==== Basic sort building blocks ====
*** insert: insert on sorted array, keeping it sorted
*** merge: merge two sorted arrays into a sorted array.
*** partition an arbitrary array into smaller and larger than a given t
 
 
==== Tarefa 7 - Busca Binaria 30Mai19 ====
* Implementar busca binaria de um vetor ordenado de floats
* Utilizar apenas linguagem C e sua propria implementacao
* Bonus: implementar em C++ usando a biblioteca padrao
 
 
==== Tarefa 8 - Ordenacao 6Jun19 ====
* Implementar o mergesort, o quicksort e o insertion sort
 
 
 
=== Part 2: Computational Geometry problems to practice C++ programming ===
*** Compute scalar and vector product of 3-vectors
*** Hash tables, Buckets for point query
*** Proximity
*** Voronoi Diagrams
*** Curve Algorithms
 
===== Homework: given a list of points, compute the closest point =====
* Naive algorithm
* Hash table from Programming Pearls
 
===== Homework: given a list of points, output all lines passing through each pair of points =====
* Line going through two points
 
==== Trabalho: Parte 1 valendo bonus, dia 2/Maio/2019, Parte2 completo 16/Maio/2019 (REMARCADA) ====
* Dado um labirinto na forma de uma matriz, onde os caminhos sao formados por espaco ' ',
e as paredes do labirindo sao formadas pela letra 'a' ou '8' conforme abaixo, e dada uma entrada e uma saida marcadas por espaco ' ' ou na parede de cima do labirinto, ou na parede de baixo, resolva o labirinto ou retorne 0 caso nao exista um caminho. Note que tanto as paredes ou os caminhos podem ter largura maior que 1 caractere.
* A parte 2 do trabalho valera nota e devera ser entregue 1 semana apos a parte 1. A parte 1 eh apenas bonus para incentivar o aluno a resolver o problema com ideias proprias.
* Sera dado um grande bonus.
 
    aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa  a
    8  8              8              8          8                  8  8
    8  8  aaaaaaaaa  8  aaaaa  aaaa8aaaa  aaaa8  aaaaa  aaaaa  8  8
    8              8      8  8          8          8  8  8      8  8
    8aaaaaaaa  a  8aaaaaaa8  8aaaaaaaa  8aaaa  a  8  8  8aaaaaaa8  8
    8      8  8              8          8  8  8  8  8          8  8
    8  a  8aaa8aaaaaaaa  a  8  aaaaaaaa8  8aaa8  8  8aaaaaaaa  8  8
    8  8              8  8  8      8          8          8      8  8
    8  8aaaaaaaaaaaa  8aaa8  8aaaa  8  aaaaa  8aaaaaaaa  8  aaaa8  8
    8          8      8  8      8  8      8          8  8          8
    8  aaaaa  8aaaa  8  8aaaa  8  8aaaaaaa8  a  a  8  8aaaaaaaaaaa8
    8      8      8  8  8      8      8      8  8  8      8      8
    8aaaaaaa8aaaa  8  8  8  aaaa8aaaa  8  aaaa8  8  8aaaa  8aaaa  8
    8          8  8          8      8  8      8  8      8          8
    8  aaaaa  8  8aaaaaaaa  8aaaa  8  8aaaa  8aaa8  aaaa8aaaaaaaa  8
    8  8      8          8          8      8  8  8              8  8
    8  8  aaaa8aaaa  a  8aaaa  aaaa8aaaa  8  8  8aaaaaaaaaaaa  8  8
    8  8          8  8  8  8  8          8              8  8      8
    8  8aaaaaaaa  8  8  8  8aaa8  8aaaaaaa8  aaaaaaaaa  8  8aaaaaaa8
    8  8      8  8  8          8          8  8      8              8
    8  8  aaaa8  8aaa8  aaaaa  8aaaaaaaa  8aaa8  a  8aaaaaaaa  a  8
    8  8                  8          8              8              8  8
    8  8aaaaaaaaaaaaaaaaaaa8aaaaaaaaaaa8aaaaaaaaaaaaaaa8aaaaaaaaaaaaaaa8aaa8
 
 
 
==== Quizz 1: C++ programming skills ====
***


== General Info ==
* Instructor: prof. [http://rfabbri.github.io Ricardo Fabbri], Ph.D. Brown University
* Meeting times: Tuesdays 2:20pm-4pm Thursdays 8:50am - 10:30am, room (205?)
* Evaluation criteria: 1 quizz at midterm (60%), practical projects (40%).
* Forum for file exchange and discussion: email and IRC #labmacambira


[[Category:Lab Macambira]] [[Category:IPRJ]]
[[Category:Lab Macambira]] [[Category:IPRJ]]

Edição atual tal como às 10h58min de 31 de outubro de 2019

////////// Under Construction //////////

Computational-geometry-concept-diagram.png

This is the main page of a graduate level course in computational geometry being taught in 2019/2 at the Polytechnic Institute IPRJ/UERJ. It is generally useful for programmers at the advanced level in the fields of machine learning, scientific simulations, graphics, computer vision and and multimedia programming.



General Info

  • Instructor: prof. Ricardo Fabbri, Ph.D. Brown University
  • Meeting times: Wednesdays 7:50-11:30, Thursdays 7:50-9:40, and 15:00-17:00, room 110.
  • Evaluation criteria: at least 2 quizzes (40%), practical projects (60%).
  • Forum for file exchange and discussion: email and IRC #labmacambira

Lecture Log

Part 1: C++ Programming Practice and Review

Wed 9Out19 (twice lecture load)

  • Hello world
    • for loop print 10x
  • Slides 1 Review C Fabbri
    • Variables, arrays/vectors
  • Farenheit to/from celcius program: homework

Wed 16Oct19

  • Show results of Farenheit to Celsius
  • Learn Codeblocks

Thu 17Oct19

  • Print function graph (K&R Histogram)
    • Horizontal
      • Learn how to write max function: non-recursive and recursive
      • Learn first simple sort algorithm using max

Wed 23Out19 (twice lecture load)

  • Due: simple sort using max
  • bucket sort (class exercise). Due. (student juliana: done)
  • Other simple sorts. Insertion, selection, bubble
    • Basic building block: insert on sorted array, keeping it sorted
  • Theory: arrays.

Thu 24Out19

  • Overdue: simple sort using max
    • Did: used max function
      • at first, max function without index
        • Sub-exercise: implement max of an array to return index, recursive and non-recursive
      • did: sort with max function, with index
    • Question: does it work with repeated entries?
    • If you have a vector of float height[num_people] and age[num_people], and there is a repeated age, can you print ages and respective heights sorted by age, without losing information?
    • What is a stable sort
  • Vector and cross product exercise
    • Exercise from qualify
  • Sort building blocks

Wed 30Out19

  • Overdue: Vertical Function graph (K&H Histogram)
  • Due: Insert on sorted array (Juliana: 9,5)
  • Due: Merge two sorted arrays as warmup for next lecture (Juliana: 5)
  • Due: Simple sort by recursive and non-recursive max is stable? argue in PDF (Juliana 0)
  • Content
    • Reviewed due homework
    • Pointers, references
    • Arrays and pointers
    • Matrices as multidimensional arrays. Pointers.
    • Malloc for arrays and matrices
    • Structs
    • Void *
    • Pointers to functions

Thu 31Out19

  • Due: better sorted insert
  • Due: max() in vertical histogram
  • Due: more efficient merge
  • Bitwise operators. Modulo operator.
  • Excercises: one regarding Matrices, another regarding number and bit manipulation.
  • Image lookup table for sorting intensities

Wed 13Out19

  • Exam: programming fundamentals

Future

  • Intro to advanced sorts: Merge sort, Quick Sort
    • Basic building blocks:
      • merge: merge two sorted arrays into a sorted array.
      • partition an arbitrary array into smaller and larger than a given t

Tasks + Homework

Part 1: C++ Programming practice and Review

Hello World

Celsius to/from Farenheit

Print Function graph (K&R Histogram): horizontally

  • Sub exercise: max function

Implement max function recursively

Sort using max function

Print Function graph (K&R Histogram): vertically

Bucket sort

Vector and cross product exercise

  • Exercise from qualify

Dados 2 vetores de inteiros A=[a1,a2,a3] e B=[b1,b2,b3] :

  1. Crie uma função que leia estes vetores do teclado
  2. Crie um função que calcule o produto escalar entre estes vetores.
  3. Crie uma função que calcule o produto vetorial entre estes vetores.
  4. Crie uma função que imprima o resultado na tela
produto escalar C = A*B=a1b1 + a2b2 + a3b3
produtor vetorial C =[a2b3 – a3b2, a3b1 – a1b3, a1b2 - a2b1]


Basic sort building blocks

      • insert: insert on sorted array, keeping it sorted
      • merge: merge two sorted arrays into a sorted array.
      • partition an arbitrary array into smaller and larger than a given t


Tarefa 7 - Busca Binaria 30Mai19

  • Implementar busca binaria de um vetor ordenado de floats
  • Utilizar apenas linguagem C e sua propria implementacao
  • Bonus: implementar em C++ usando a biblioteca padrao


Tarefa 8 - Ordenacao 6Jun19

  • Implementar o mergesort, o quicksort e o insertion sort


Part 2: Computational Geometry problems to practice C++ programming

      • Compute scalar and vector product of 3-vectors
      • Hash tables, Buckets for point query
      • Proximity
      • Voronoi Diagrams
      • Curve Algorithms
Homework: given a list of points, compute the closest point
  • Naive algorithm
  • Hash table from Programming Pearls
Homework: given a list of points, output all lines passing through each pair of points
  • Line going through two points

Trabalho: Parte 1 valendo bonus, dia 2/Maio/2019, Parte2 completo 16/Maio/2019 (REMARCADA)

  • Dado um labirinto na forma de uma matriz, onde os caminhos sao formados por espaco ' ',

e as paredes do labirindo sao formadas pela letra 'a' ou '8' conforme abaixo, e dada uma entrada e uma saida marcadas por espaco ' ' ou na parede de cima do labirinto, ou na parede de baixo, resolva o labirinto ou retorne 0 caso nao exista um caminho. Note que tanto as paredes ou os caminhos podem ter largura maior que 1 caractere.

  • A parte 2 do trabalho valera nota e devera ser entregue 1 semana apos a parte 1. A parte 1 eh apenas bonus para incentivar o aluno a resolver o problema com ideias proprias.
  • Sera dado um grande bonus.
   aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa   a
   8   8               8               8           8                   8   8
   8   8   aaaaaaaaa   8   aaaaa   aaaa8aaaa   aaaa8   aaaaa   aaaaa   8   8
   8               8       8   8           8           8   8   8       8   8
   8aaaaaaaa   a   8aaaaaaa8   8aaaaaaaa   8aaaa   a   8   8   8aaaaaaa8   8
   8       8   8               8           8   8   8   8   8           8   8
   8   a   8aaa8aaaaaaaa   a   8   aaaaaaaa8   8aaa8   8   8aaaaaaaa   8   8
   8   8               8   8   8       8           8           8       8   8
   8   8aaaaaaaaaaaa   8aaa8   8aaaa   8   aaaaa   8aaaaaaaa   8   aaaa8   8
   8           8       8   8       8   8       8           8   8           8
   8   aaaaa   8aaaa   8   8aaaa   8   8aaaaaaa8   a   a   8   8aaaaaaaaaaa8
   8       8       8   8   8       8       8       8   8   8       8       8
   8aaaaaaa8aaaa   8   8   8   aaaa8aaaa   8   aaaa8   8   8aaaa   8aaaa   8
   8           8   8           8       8   8       8   8       8           8
   8   aaaaa   8   8aaaaaaaa   8aaaa   8   8aaaa   8aaa8   aaaa8aaaaaaaa   8
   8   8       8           8           8       8   8   8               8   8
   8   8   aaaa8aaaa   a   8aaaa   aaaa8aaaa   8   8   8aaaaaaaaaaaa   8   8
   8   8           8   8   8   8   8           8               8   8       8
   8   8aaaaaaaa   8   8   8   8aaa8   8aaaaaaa8   aaaaaaaaa   8   8aaaaaaa8
   8   8       8   8   8           8           8   8       8               8
   8   8   aaaa8   8aaa8   aaaaa   8aaaaaaaa   8aaa8   a   8aaaaaaaa   a   8
   8   8                   8           8               8               8   8
   8   8aaaaaaaaaaaaaaaaaaa8aaaaaaaaaaa8aaaaaaaaaaaaaaa8aaaaaaaaaaaaaaa8aaa8


Quizz 1: C++ programming skills