Three More List Manipulation Exercises

Programming Praxis

We have three more list-manipulation exercises today, for those students midway through their beginning programming course who need practice with linked lists:

  1. Define a function that takes two lists, the second of which is a list of non-negative integers the same length as the first list, and returns a list of elements from the first list, in reverse order, each repeated a number of times as specified by the corresponding element of the second list.
  2. Rearrange the integers in a list so that all the odd numbers appear before all the even numbers, with both odd and even numbers in the same relative order in the output as they were in the input.
  3. Write a function that returns the nth item from the end of a list.

Your task is to write the three specified programs. When you are finished, you are welcome to read or run a suggested solution…

Ver la entrada original 421 palabras más

Two Interview Questions

Programming Praxis

It’s been a while since we had any interview questions. We have two today, since they are so simple:

1) Given a number n, find the smallest 3-digit number such that the product of its digits is equal to n. For example, given n = 100, the solution is 455.

2) Given two arrays, one with n items and one with n+2 items including the same items as the array with n items plus two additional items, find the two additional items. Assume none of the items are duplicates.

Your task is to write solutions to the two interview questions given above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

The simplest solution for the first question uses three nested loops, computing the product and returning the…

Ver la entrada original 700 palabras más

Técnica pomodoro

En estos días, me he sentido muy “improductivo”, debido a que he tenido muchas distracciones y siento que me estoy atorando en varias tareas.

Antes de retomar esas tareas, he considerado necesario el buscar alguna(s) técnica(s) que me permita recuperar mi productividad en base a pequeños ajustes.

Una de las técnicas que voy a comenzar a probar es la técnica pomodoro, desarrollada por Francisco Cirillo a finales de 1980. La idea de esta técnica es dividir tu tiempo en intervalos de 25 minutos (llamados pomodoros) separados por pequeñas pausas de 5 minutos y después de 4 pomodoros, tomar una larga pausa de 15-30 minutos.

Para aplicar esta técnica es necesario en cuenta las siguientes etapas:

  • Planeamiento
  • Anotación
  • Registro
  • Proceso
  • Visualización

En la etapa de planeamiento, se listan todas las tareas que se tienen que hacer “para hoy”, lo cuál permite a los usuarios estimar los esfuerzos que cada tarea puede requerir. En la etapa de anotación se incia la tarea a enfocarse, dedicando los pomodoros necesarios para realizarla.

Cada vez que se termina un pomodoro, hay que registrar el fin del pomodoro con una etiqueta indicando que se terminó el pomodoro. Generalmente esto se realiza mediante una X.

Y en la etapa de visualización, se hace un análisis estadístico acerca de las actividades realizadas para determinar el tiempo aplicado.

Para hacer lo anterior, lo recomendado es realizar los siguientes cinco pasos:

  • Decidir la tarea a realizar
  • Poner el pomodoro a ejecutar (25 minutos)
  • Trabajar en la tarea hasta que el pomodoro termine y anotar una X en la lista de tareas
  • Tomar una pausa breve (5 minutos)
  • Cada cuatro “pomodoros”, tomar una pausa más larga (15-30 minutos).

Un objetivo esencial de esta técnica es eliminar las interrupciones, tanto internas como externas. Esto se hace registrándolas y posponiéndolas siempre que sea posible. En caso de que la interrupción sea crítica, se debe resolver la interrupción y reiniciar el trabajo con los pomodoros.

A set of top Computer Science blogs

Computing: The Science of Nearly Everything

This started out as a list of top Computer Science blogs, but it more closely resembles a set: the order is irrelevant and there are no duplicate elements; membership of this set of blogs satisfies all of the following conditions:

  1. they are written by computer scientists and focus on computer science research;
  2. they are of consistently high quality;
  3. I regularly read them.

N.B. I have deliberately excluded blogs primarily focusing on computer science education (for another time).

  • The Endeavour by John D. Cook (@JohnDCook)

    John’s blog cuts across using computing, programming and mathematics to solve real-world problems, pulling in his wide expertise as a mathematics professor, programmer, consultant, manager and statistician. Some great posts across the technical and socio-technical spectrum. Also runs a number of useful Twitter tip accounts, including @CompSciFact, @UnixToolTip, @RegexTip and @TeXtip.

  • Serious Engineering by Anthony Finkelstein (@profserious)

    Anthony is Dean of the Faculty of…

Ver la entrada original 450 palabras más

Machine Learning

Notas sobre Machine Learning de Stanford

Definiciones de Machine Learning

Arthur Samuel (1959): Campo de estudio que da a las computadoras la habilidad de aprender sin ser explicitamente programada.

Tom Mitchel (1998): Se dice que un programa de computadora aprende de una experiencia E respecto a alguna tarea T y alguna medida de rendimiento P, si el rendimiento de sobre T medido por P mejora con la experiencia E.

Tipos de aprendizaje máquina

  • Aprendizaje supervisado
  • Aprendizaje no supervisado
  • Reforzamiento del aprendizaje
  • Sistemas de recomendación

Aprendizaje supervisado

  • Necesitan de un conjunto correcto de respuestas
  • Problemas de regresión: Predecir un resultado de valor continuo
  • Problemas de clasificación: Predecir un resultado de valor discreto.

Aprendizaje no supervisado

  • Algoritmos de agrupamiento (Clustering)
  • Algoritmo de separación de voces
  • Lenguage de prototipado rápido.

Regresión lineal

Notación:

  • m = número de ejemplos para el entrenamiento
  • y’s = variables de entrada / características
  • y’s = variables de salida / variable objetivo
  • (x,y) = un ejemplo de entrenamiento
  • (x^{i}, y^{i}) - i^{th} elemento

Training set -> Learning algorithm -> h (hypothesis)

  • h: x -> y
  • How do we represent h? h_{\Theta}(x) = \Theta_{0} + \Theta_{1x}
  • A veces h_{\Theta}(x) = h(x)
  • minimizar \Theta_{0} \Theta_{1} | \sum\limits_{i=1}^{m}(h_{\Theta^{(i)}} - y^{(i)})^{2}

Regresión lineal con múltiples variables

Notación

  • n = número de características
  • x^{(i)} = entrada de características del i^{esimo} ejemplo de entrenamiento
  • x_{j}^{(i)} = valor de la característica j en el i^{esimo} ejemplo de entrenamiento

Hipótesis generalizada

  • Anteriormente: h_{\theta} (x) = \theta_{1} + \theta_{1x}
  • Ahora: h_{\theta} = \theta_{0} + \theta_{1x_{1}} + \theta_{2x_{2}} + \ldots + \theta_{nx_{n}}
  • Por conveniencia de notación, definimos x_{0} = 1
  • Función de costo J(\theta_{0}, \theta_{1}, \ldots, \theta_{n}) = \frac{1}{2m}\sum\limits_{i=1}^{m}(h_{\theta}(x^{(i)}) - y^{(i)})^{2}

Gradiente descendiente multivariable

  • Gradiente descendiente (Actualización simultánea \forall j = 0, \ldots, n)

Escalamiento de características.

  • Asegurar que las características están en una escala similar.
  • Posible solución, ortonormalizar los valores de x_{j}
  • Normalización por media: x_{i} = \frac{x_{i} - M_{i}}{s_{i}}, donde M_{i} es el valor promedio para x_{i} en el conjunto de datos, y s_{i} puede ser la diferencia entre max y el min de los valores de tu rango de datos o la desviación estándar de tu conjunto de datos.

Ecuación normal

  • \theta = (X^{T}X)^{-1}X^{T}y
  • En octave \theta = pinv(X’ * X) * X’ * y
  • Gradiente descent vs Normal equation
Gradient descent Normal equation
Needs to choose α No need to choose α
Needs many iterations Don’t need to iterate
Trabaja bien cuando el número de características es grande Lento si el número de características es grande
  • Needs to choose α | No need to choose α
  • Needs many iterations | Don’t need to iterate
  • Trabaja bien cuando el número de car

Tikz test

Here’s a tree, exported to both html and pdf.

Otros

node label shape fillcolor
S_start start ellipse green
S_fill fill form    
S_send send form    
S_complete form complete? diamond yellow
S_do do task   red
S_end end ellipse  
from to label
S_start S_fill  
S_fill S_send  
S_send S_complete  
S_complete S_fill N
S_complete S_do Y
S_do S_end  

example-diagram.png

Diana Cryptosystem

Programming Praxis

[ Today’s exercise comes from the blog of long-time reader Ben Simon, after he declined my offer to guest-author the exercise and told me to steal it. The code and most of the text is his, so he gets the credit, not me. ]

It’s been a while since we had an exercise from our cryptography topic. Today’s exercise is the Diana Cryptosystem, also known as the trigraph cipher, which was used militarily by US forces during the Vietnam War and is theoretically unbreakable when used properly.

There are two pieces to the system: the trigraph itself, which is pictured at right, and a one-time pad, like this:

WHTVI AUCFU RETFK OMSAL
MYMNE ZIEGP UKVTF WZHOK
GORWY WETFR COYET OOWHY
ZPDDA CMMXT VYTJI RRQGU

To use the cipher, a section of the one-time pad is chosen and the two five-character groups that begin the section are transmitted unchanged. Thereafter, the…

Ver la entrada original 829 palabras más

Recursion versus iteration

A Programmers Place

The first programming language to allow functions to be recursively defined was McCarthy’s LISP in 1959. Its introduction was not controversial: nobody but John McCarthy had any say in what the language was going to be. In addition to his work on LISP, McCarthy was on the committee finalizing the Algol language in 1959 and 1960. In spite of the fact that a majority was opposed to it, the definition of Algol 60 ended up allowing recursively defined procedures. In [1] I gave an acount of how this happened.

Why was recursion such a big deal? For us this is hard to understand: for decades the programming language C, not exactly a paradigm of avant-garde, has allowed recursion. Still, remnants of unease remain. Still, in some introductory courses, recursion plays the role of a pons asinorum. Have instructors been traumatized by a sarcastic teacher finding, oh horrors…

Ver la entrada original 2.420 palabras más